Алгоритмы - Структуры - LeetCode - 14. Longest Common Prefix

Один из десятка тысяч разборов этой задачи, в большей степени перевод leetcode, очень недалёкий, но кому-то как и мне может надо прорешать задачу N раз, чтобы понять и не забывать её.

Дано: Напишите функцию для поиска самой длинной строки с общим префиксом среди массива строк. Если общего префикса нет, то возвращается пустая строка "".

Пример:
Вход: strs = ["потолок", "поток", "полет"].
Выходные данные: "по"

Ограничения:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] состоит только из строчных букв.

1) Наивное решение:

def longestCommonPrefix(strs: List[str]) -> str:
ans= ""
if strs is None or len(strs) == 0:
return ans
minimumLength = len(strs[0])
for i in range(1, len(strs)):
minimumLength = min(minimumLength, len(strs[i]))
for i in range(0, minimumLength):
current = strs[0][i]
for j in range(0, len(strs)):
if strs[j][i] != current:
return ans
ans+= current
return ans

Первое, проверяем, что у нас есть элементы в массиве if strs is None or len(strs) == 0:, если есть, то мы ищем элемент, в нашем случае строку, минимальный длины в массиве из всех, так длиннее этой строки, совпадений быть не может min(minimumLength, len(strs[i])). Дальше перебираем эту строку и сравниваем с элементами других строк с помощью цикла в цикле if strs[j][i] != current.

Улучшаем:

def longestCommonPrefix(self, strs: List[str]) -> str:
if strs == None or len(strs) == 0: return ""
for i in range(len(strs[0])):
c = strs[0][i]
for j in range(1,len(strs)):
if i == len(strs[j]) or strs[j][i] != c:
return strs[0][:i]
return strs[0] if strs else ""

Перебираем первую строку массива(списка) и сравниваем поэлементно с другими строками массива, если другие строки короче или не содержат того же символа, останавливаемся и возвращаем первую строку до того элемента, где оборвалось совпадение.

2) С применением функции zip().

Функция zip() в Python создает итератор, который объединяет элементы из нескольких источников данных.

def longestCommonPrefix(self, strs: List[str]) -> str:
n = 0
for i in zip(*strs):
if len(set(i)) > 1:
break
n += 1
return strs[0][:n]

Решение основано на уникальности элементов множества set():

Сначала задаем целочисленную переменную, в которой будем хранить количество повторений элементов строк, дальше функция zip() соединяет поэлементно в кортежи строки списка (*strs - распаковываем все аргументы(элементы) списка.), пример: (["цветок", "поток", "полет"] -> [(ц, п, п), (в, о, о).....(о, к, е)] и режет все элементы, которые длиннее минимальной строки. Дальше благодаря свойству множества проверяем длину каждого кортежа, например наш кортеж (ц, п, п) преобразуется в множество {ц, п}, а если бы все первые элементы строк массива начинались бы с ц, то множество было бы {ц}..Таким образом, если длина множества меньше 2, то продолжаем сравнение, иначе возвращаем результат.

3) С применением метода строки startswith

def longestCommonPrefix(self, strs: List[str]) -> str:
ans= strs[0]
for i in strs:
while not i.startswith(ans):
ans= ans[:-1]
return ans

Выделяем первую строку массива strs[0], и начинаем цикл по всем строкам массива, проверяя начинаются ли остальные строки с того же первого элемента, что и первая строка i.startswith(ans), если да, то меняем первый элемент первой строки на второй и так далее.

Временная сложность: все алгоритмы дают сложность цикла в цикле, что составляет O(n)*O(m)

Пространственная сложность: используем строку и числовую переменную, что даёт O(1)

3) С применением сортировки

def longestCommonPrefix(self, v: List[str]) -> str:
ans = ""
v = sorted(v)
first = v[0]
last = v[-1]
for i in range(min(len(first), len(last))):
if (first[i] != last[i]):
return ans
ans += first[i]
return ans

Создаём переменную для хранения подстроки одинаковых символов ans.
Сортируем наш массив, это нужно для того, чтобы первый элемент первой строки совпадал с первым элементом последней строки...иначе нету одинаковых элементов. Перебираем символы первой и последней строк в отсортированном списке по минимальным строкам в массиве. Если текущий символ первой строки не равен текущему символу последней строки, то возвращается найденный на данный момент общий префикс. Иначе текущий символ добавляется в строку ans.

Временная сложность: цикл даёт сложность O(n), , sorted() O(nlogn?), что даёт общую сложность O(nlogn).

Пространственная сложность: используем строку и 2 числовых переменных, что даёт O(1)