Цель — найти самый длинный общий префикс, который есть у всех строк в списке. Подход использует первую строку как начального кандидата на префикс и постепенно сокращает его, пока он не совпадёт со всеми остальными строками.
prefix равным первой строке в спискеss не начинается с текущего prefix, удали один символ с конца prefixs.startswith(prefix) не вернёт True, или пока prefix не станет пустымprefix после проверки всех строкdef longest_common_prefix(strs):
if not strs:
return ""
prefix = strs[0]
for s in strs[1:]:
while not s.startswith(prefix):
prefix = prefix[:-1]
if not prefix:
return ""
return prefix
Дан ["flower", "flow", "flight"]:
prefix начинается с "flower""flow" → сокращается до "flow""flight" → сокращается до "flo", затем до "fl""fl"O(S), где S — общее количество символов во всех строкахO(1) — дополнительные структуры данных не используются""""Алгоритм инициализирует префикс первой строкой из списка и удаляет символы с конца, пока префикс не совпадёт со всеми остальными строками.
Новый — ещё не проверен сообществом
Вы