Программирование
Задачи с собеседований: Leetcode — Наибольший общий префикс
Напишите функцию для поиска самой длинной строки с общим префиксом среди массива строк.
Задача
Напишите функцию для поиска самой длинной строки, являвшейся общим началом для всего массива строк — наибольший общий префикс.
Если общего префикса нет, верните пустую строку.
Пример:
Ввод: strs = [«flower»,»flow»,»flight»]
Вывод: «fl»
Пример:
Вход: strs = [«dog»,»racecar»,»car»]
Выходные данные: «»
Пояснения: среди входных строк нет общего префикса.
Ограничения
- 1 <= strs.length <= 200
- 0 <= strs[i].length <= 200
- Строка strs[i] состоит только из строчных английских букв
Ссылка
Наибольший общий префикс на Leetcode: https://leetcode.com/problems/longest-common-prefix/
Наибольший общий префикс: решение
Самое простое и очевидное решение — перебрать все строки и увеличивать ответ по мере того, как с ним совпадают строки в массиве.
func longestCommonPrefix(_ strs: [String]) -> String { guard let firstStr = strs.first else { return "" } var prefix = "" for i in 0..<firstStr.count { let char = firstStr[firstStr.index(firstStr.startIndex, offsetBy: i)] for str in strs { if i >= str.count || str[str.index(str.startIndex, offsetBy: i)] != char { return prefix } } prefix.append(char) } return prefix }
Как это работает:
- Начинаем с пустого префикса.
- Проходим по символам первой строки, добавляя их по одному в префикс.
- На каждом символе проверяем, что этот символ есть в той же позиции у всех других строк:
- Если находим несовпадение (либо строка короче, либо символ отличается), останавливаемся и возвращаем текущий префикс.
- Если все символы первой строки совпадают у всех строк, возвращаем полный наибольший общий префикс.
Пример
Для строк ["flower", "flow", "flight"]
:
- Берём
f
, проверяем — он есть в начале каждой строки. - Добавляем
l
, проверяем — он тоже есть в начале каждой строки. - Пытаемся добавить
o
, но видим, что в"flight"
на этой позиции другой символ. Останавливаемся и возвращаем"fl"
.
Такое решение явно не оптимально и занимает много времени и памяти:
Временная сложность этого решения O(S)
, где S — общее количество символов во всех строках. Внешний цикл проходит по каждому символу первой строки (до её длины, обозначим её как L). Внутренний цикл на каждом символе проверяет все строки, что в худшем случае затрачивает время, пропорциональное n (количество строк). В каждом шаге мы проверяем символы, пока не найдём несовпадение или не достигнем конца строки. Таким образом, общее время будет зависеть от количества символов, которые нам нужно проверить — это сумма всех символов во всех строках, O(S), где O(S), где S=n × L
Другое решение
Можно пойти в обратном направлении и взять первую строку за основу и уменьшать ее.
func longestCommonPrefix(_ strs: [String]) -> String { guard let firstStr = strs.first else { return "" } var prefix = firstStr for str in strs { while !str.hasPrefix(prefix) { prefix = String(prefix.dropLast()) if prefix.isEmpty { return "" } } } return prefix }
Как это работает:
- Начинаем с первой строки в списке как с «предполагаемого наибольшего общего префикса». Это значит, что мы считаем её общим началом для всех строк, пока не доказано обратное.
- Проходимся по каждой строке в списке и проверяем, совпадает ли её начало с нашим предполагаемым префиксом.
- Если нет, убираем последнюю букву у префикса и проверяем снова.
- Продолжаем укорачивать наибольший общий префикс, пока он не станет общим началом для текущей строки.
- Когда проверим все строки, оставшийся префикс — это самый длинный общий префикс для всех строк.
Пример
Если список строк — ["flower", "flow", "flight"]
, мы начнём с "flower"
. Затем:
- Сравним с
"flow"
и сократим до"flow"
, так как это общее начало для обеих строк. - Сравним с
"flight"
и сократим до"fl"
, потому что только эти две буквы совпадают.
В итоге, ответ — «fl», так как это самый длинный префикс, который есть у всех строк.
Этот алгоритм имеет такую же временную сложность O(S)
, где S — общее количество символов во всех строках. Однако он может быть быстрее в практике из-за оптимизации, связанной с его структурой:
- Уменьшение префикса: Второй алгоритм сокращает префикс только тогда, когда обнаруживает несовпадение. То есть, он быстро останавливается, если префикс больше не совпадает для какой-либо строки. Это позволяет избежать ненужных проверок, так как префикс сокращается «скользящим» образом — после каждого несовпадения он сразу же сокращается на один символ.
- Меньше операций в худшем случае: Если строки имеют большой общий префикс, первый алгоритм перебирает каждый символ, добавляя его в префикс и проверяя для всех строк, тогда как второй алгоритм сразу использует всю первую строку как предполагаемый префикс и сокращает его, если это необходимо. В ситуациях, когда префикс отличается ближе к концу строки, второй алгоритм быстрее находит ответ, так как сразу работает с длинными префиксами.
- Лучшая производительность на коротких строках: В случаях, когда строки короткие и различия появляются рано, второй алгоритм быстрее завершает работу, так как он останавливается сразу после сокращения префикса.
Таким образом, хотя оба алгоритма имеют временную сложность O(S)
, первый алгоритм лучше оптимизирован для случаев, когда строки имеют префиксы разной длины или когда различия между строками появляются ближе к началу строк.
Дополнительно
← Задачи с собеседований: Leetcode — Сложите два числа
← Как решать задачи на Leetcode