Задачи с собеседований: 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
}

Как это работает:

1. Начинаем с пустого префикса.
2. Проходим по символам первой строки, добавляя их по одному в префикс.
3. На каждом символе проверяем, что этот символ есть в той же позиции у всех других строк:
   • Если находим несовпадение (либо строка короче, либо символ отличается), останавливаемся и возвращаем текущий префикс.
4. Если все символы первой строки совпадают у всех строк, возвращаем полный наибольший общий префикс.

Пример

Для строк ["flower", "flow", "flight"]:

• Берём f, проверяем — он есть в начале каждой строки.
• Добавляем l, проверяем — он тоже есть в начале каждой строки.
• Пытаемся добавить o, но видим, что в "flight" на этой позиции другой символ. Останавливаемся и возвращаем "fl".

Такое решение явно не оптимально и занимает много времени и памяти:

Временная сложность этого решения O(S), где S — общее количество символов во всех строках. Внешний цикл проходит по каждому символу первой строки (до её длины, обозначим её как L). Внутренний цикл на каждом символе проверяет все строки, что в худшем случае затрачивает время, пропорциональное n (количество строк). В каждом шаге мы проверяем символы, пока не найдём несовпадение или не достигнем конца строки. Таким образом, общее время будет зависеть от количества символов, которые нам нужно проверить — это сумма всех символов во всех строках, O(S), где O(S), где $в\; худшем\; случае.$

Другое решение

Можно пойти в обратном направлении и взять первую строку за основу и уменьшать ее.

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
}

Как это работает:

1. Начинаем с первой строки в списке как с «предполагаемого наибольшего общего префикса». Это значит, что мы считаем её общим началом для всех строк, пока не доказано обратное.
2. Проходимся по каждой строке в списке и проверяем, совпадает ли её начало с нашим предполагаемым префиксом.
   • Если нет, убираем последнюю букву у префикса и проверяем снова.
   • Продолжаем укорачивать наибольший общий префикс, пока он не станет общим началом для текущей строки.
3. Когда проверим все строки, оставшийся префикс — это самый длинный общий префикс для всех строк.

Пример

Если список строк — ["flower", "flow", "flight"], мы начнём с "flower". Затем:

• Сравним с "flow" и сократим до "flow", так как это общее начало для обеих строк.
• Сравним с "flight" и сократим до "fl", потому что только эти две буквы совпадают.

В итоге, ответ — «fl», так как это самый длинный префикс, который есть у всех строк.

Этот алгоритм имеет такую же временную сложность O(S), где S — общее количество символов во всех строках. Однако он может быть быстрее в практике из-за оптимизации, связанной с его структурой:

1. Уменьшение префикса: Второй алгоритм сокращает префикс только тогда, когда обнаруживает несовпадение. То есть, он быстро останавливается, если префикс больше не совпадает для какой-либо строки. Это позволяет избежать ненужных проверок, так как префикс сокращается «скользящим» образом — после каждого несовпадения он сразу же сокращается на один символ.
2. Меньше операций в худшем случае: Если строки имеют большой общий префикс, первый алгоритм перебирает каждый символ, добавляя его в префикс и проверяя для всех строк, тогда как второй алгоритм сразу использует всю первую строку как предполагаемый префикс и сокращает его, если это необходимо. В ситуациях, когда префикс отличается ближе к концу строки, второй алгоритм быстрее находит ответ, так как сразу работает с длинными префиксами.
3. Лучшая производительность на коротких строках: В случаях, когда строки короткие и различия появляются рано, второй алгоритм быстрее завершает работу, так как он останавливается сразу после сокращения префикса.

Таким образом, хотя оба алгоритма имеют временную сложность O(S), первый алгоритм лучше оптимизирован для случаев, когда строки имеют префиксы разной длины или когда различия между строками появляются ближе к началу строк.

Дополнительно

← Еще задачи с собеседований

← Задачи с собеседований: Leetcode — Сложите два числа

← Как решать задачи на Leetcode