Боталка(Студенты) — Поступашки

Задача с собеседования в 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