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