Продолжаем наш непотопляемый цикл про задачки с собеседований. Эти задачи мы берём с сайта Leetcode — главного сборника таких задач с комментариями разработчиков. Но там всё по-английски, а мы разберём по-русски и насколько возможно просто.
Сегодняшнюю задачу любят давать тем, кому придётся работать с текстом, например в разработке поисковых систем. Условие:
Есть массив со словами, в котором есть хотя бы одно слово. Надо найти максимально длинное общее начало каждого слова. Если такого нет — вывести пустую строку.
Пример: у нас есть массив ['дом', 'домен', 'домра', 'доширак']. Общее начало каждого слова — 'до'.
Ещё пример: массив ['документ', 'дока', 'кум', 'ум']. Ответом будет пустая строка, потому что у всех этих слов нет единой общей части в начале слова.
Попробуйте решить это самостоятельно, а потом возвращайтесь к ответам.
Простое решение
Раз одинаковое начало должно быть у всех слов, то за основу можно взять первое слово, а все остальные начала сравнивать с ним. Причём сравнивать нужно посимвольно:
- Берём первое слово как основное.
- Берём оттуда первую букву.
- Смотрим, совпадает ли она с первыми буквами во всех других словах.
- Если совпадает — добавляем эту букву к ответу с общей частью.
- Если не совпадает — прекращаем работу и выводим то, что нашли к этому моменту.
- Если ничего не нашли, то выводим пустую строку.
Чтобы такое сделать в Python, нам понадобится функция enumerate() — если ей на вход дать слово, то она сможет в цикле по очереди возвращать очередной символ и его порядковый номер. Это именно то, что нам нужно, — перебрать все символы в первом слове по порядку.
Ещё из нового — команда else в конце цикла. Мы привыкли, что else используют в условиях, но иногда эту команду добавляют и к циклу. Смысл в том, что если цикл отработал штатно и ни разу не прервался, то после его работы выполняется то, что написано после else. Это нам пригодится, чтобы понять, нужно нам добавлять очередной символ к общему началу или с циклом были проблемы и добавлять его не нужно.
Вот как выглядит реализация такого алгоритма на Python:
# исходный массив со строками
strs = ['дом', 'домен', 'домра', 'доширак']
# функция, которая найдёт общее начало
def simplelongestCommonPrefix (strs):
# на старте общее начало пустое
res = ""
# получаем пары «номер символа» — «символ» из первого слова
for i, c in enumerate(strs[0]):
# перебираем следующие слова в списке
for s in strs[1:]:
# если это слово короче, чем наш текущий порядковый номер символа
# или если символ на этом месте не совпадаем с символом на этом же месте из первого слова
if len(s)<i+1 or s[i] != c:
# выходим из функции и возвращаем, что нашли к этому времени
return res
# если цикл выполнился штатно
else:
# добавляем текущий символ к общему началу
res += c
# возвращаем результат
return res
# выводим результат работы функции
print(simplelongestCommonPrefix(strs))Хитрое решение
Для хитрого решения нам понадобятся две функции — zip(*) и set().
Функция zip(*) берёт список и формирует из него много других списков, складывая их так: первый элемент к первому, второй ко второму и так далее. Покажем работу на примере нашего списка:
- Функция возьмёт из него все слова по отдельности: 'дом', 'домен', 'домра', 'доширак'.
- Возьмёт первую букву каждого слова и составит из них отдельный список: {'д','д','д','д'}.
- Потом возьмёт вторую букву каждого слова и составит список уже из них: {'о','о','о','о'}.
- Так она будет делать до тех пор, пока не закончатся буквы в самом коротком слове. Как только хоть одно слово закончилось — функция заканчивает работу.
Получается, что так мы можем получить сразу все сгруппированные буквы по порядку каждого слова. Теперь нам нужно проверить, разные там буквы в этих списках или нет. Если все буквы одинаковые, значит, они подходят к каждому слову, и значит, что их можно добавить к ответу. Если есть хоть одна отличающаяся буква — всё, общее начало на этом закончилось.
Чтобы такое проверить, используем функцию set() — она составит из переданных ей аргументов список с уникальными значениями. Если длина такого списка будет равна 1, значит, все переданные символы были одинаковые — и их можно добавлять к ответу.
Читайте комментарии, чтобы разобраться в этом хитром коде:
# исходный массив со строками
strs = ['дом', 'домен', 'домра', 'доширак']
# функция, которая найдёт общее начало
def longestCommonPrefix(strs):
# на старте общее начало пустое
prefix=[]
# разбираем слова побуквенно в отдельные списки и перебираем их по очереди
for x in zip(*strs):
# смотрим, сколько уникальных элементов у нас получилось в наборе на этом этапе
if len(set(x)) == 1:
# если уникальный элемент один — добавляем его к общему началу
prefix.append(x[0])
# если уникальных элементов было больше одного
else:
# прерываем цикл и выходим из него
break
# возращаем результат работы функции
# если общее начало пустое, то на выходе получим тоже пустую строку
return "".join(prefix)
# выводим результат работы функции
print(longestCommonPrefix(strs))
