Задача с собеседования в OYO
Напишите функцию для поиска наибольшего общего префикса среди массива строк. Если общего префикса нет, верните пустую строку "".
Пример 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"
Пример 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: У входных строк отсутствует общий префикс.
Ограничения:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] состоит только из строчных английских букв, если эта строка не пуста.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Основная идея: общий префикс не может быть длиннее самой короткой строки. Находим её через функцию min.
shortest - самая короткая строка.
Внешним циклом проходим по индексам и символам shortest, внутренним циклом - по строкам массива, проверяя, что у всех строк на этой же позиции стоит тот же символ:
Если встречаем несовпадение: выходим из цикла и возвращаем срез shortest[:i], состоящий из накопленного с прошлых итераций префикса;
Если все символы совпали: возвращаем shortest целиком, как общий префикс.
Сложность
O(n * m) - по времени (где n - кол-во строк в массиве, а m - длина самой короткой)
O(1) - по памяти (храним переменную shortest)
Код
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
shortest = min(strs, key=len)
for i, char in enumerate(shortest):
for word in strs:
if word[i] != char:
return shortest[:i]
return shortest
@algoses
4August 20, 2026 3.5K 4 13
