Поиск самого длинного общего префикса в строках

Еще одна задача, для которой брутфорс решение является оптимальным. Такие задачи часто дают в качестве первой «разогревочной» задачи на собеседованиях.

Сложность: 🟢 Легкая


ℹ️ Описание

Напишите функцию, которая принимает на вход массив строк и возвращает в ответ максимально длинный общий префикс


⚠️ Ограничения

🔹Длина массива от 1 до 200 элементов
🔹Длина строки в массиве от одного до 200 символов
🔹Строка состоит только из символов латинского алфавита


1️⃣ Пример

Входящие данные: ["flower","flow","flight"]
Ответ: "fl"
Объяснение: ["flower","flow","flight"]

2️⃣ Пример

Входящие данные: ["dog","racecar","car"]
Ответ: ""
Объяснение: У строк нет общего префикса


✅ Решение

Для решения данной задачи нам достаточно будет сравнить соответствующие символы в каждой из строк массива, начиная с первого, заканчиваю первым не совпадающим. Если во всех строках символы совпадают - значит они входят в общий префикс. Как только мы находим символ, который не совпадает хотя бы в одной из строк - общий префикс заканчивается. Главное, не забыть, что строки в массиве могут быть разной длины.

Посмотреть реализацию

🅾️ Оценка сложности

По времени
Чтобы найти наибольший общий префикс, нам нужно в n строках проверить посимвольно до m символов (где m - длина самой короткой строки в массиве). Таким образом, получаем сложность O(m*n).

По памяти
Сложность по памяти O(m), где m - длина самой короткой строки в массиве (максимально возможная длина префикса).

#strings #arrays #easy