Задача с собеседования про перебор букв в словах

Продолжаем наш непотопляемый цикл про задачки с собеседований. Эти задачи мы берём с сайта 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))

Любишь Python? Зарабатывай на нём!

Изучите самый модный язык программирования и станьте крутым бэкенд-разработчиком. Старт — бесплатно.

Попробовать бесплатно