Longest Common Prefix

Q: Какова временная сложность алгоритма поиска наибольшего общего префикса?

Оба прохода выполняются за время O(S) , где S — общее количество букв, и используют O(1) дополнительной памяти помимо ответа. Проход по столбцам также ограничен величиной n × (L+1) для ответа длины L , поэтому он останавливается раньше, если слова расходятся ближе к началу.

Q: Что должна возвращать Longest Common Prefix, если общего префикса нет?

Пустая строка "" . Это происходит, как только два слова начинаются с разных букв, как в stack , queue и heap .

Q: Что лучше: горизонтальное или вертикальное сканирование?

У обоих алгоритмов одинаковая худшая временная сложность — O(S) . Вертикальное сканирование — более безопасный выбор: оно останавливается на первом столбце, где какое-либо слово не совпадает, тогда как при горизонтальном сканировании длинный префикс может сравниваться со многими словами, прежде чем несовпадение в более позднем слове прервёт сравнение.

ЛегкоМассивы и строки

+10

Дан массив слов strs. Верните самую длинную строку, с которой начинается каждое слово. Если не все слова начинаются с одной и той же буквы, верните пустую строку "". Слово считается префиксом самого себя, поэтому ответом для одного слова будет оно само.

Функция

longestCommonPrefix(strs: string-array) → string

strsstring-array: слова для сравнения
Возвращаетstring: самый длинный префикс, общий для всех слов, или пустая строка

Ограничения

1 ≤ strs.length ≤ 200
1 ≤ strs[i].length ≤ 200
Каждое слово содержит только строчные английские буквы.

Примеры

Ввод: strs = ["interview", "internet", "interval", "internal"]
Вывод: "inter"
Пояснение: Все четыре слова начинаются с inter. На следующей позиции в словах interview и interval стоит v, а в словах internet и internal — n, поэтому префикс заканчивается на этом месте.

Ввод: strs = ["stack", "queue", "heap"]
Вывод: ""
Пояснение: Слова начинаются с s, q и h. Они различаются уже первой буквой, поэтому ответ пуст.

Ввод: strs = ["prefix", "pre", "prepare"]
Вывод: "pre"
Пояснение: pre — самое короткое слово, и два других начинаются с него, поэтому это и есть весь ответ. Общий префикс никогда не может быть длиннее самого короткого слова.

Дополнительный вопрос

Предположим, список остаётся неизменным, а запросов поступает много. Как находить для каждого запроса самый длинный общий префикс с каким-либо словом из списка, не просматривая список заново?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Буква входит в ответ, только если она есть в каждом слове на той же позиции, а ответ заканчивается на первой позиции, где слова расходятся или одно из них заканчивается. Оба подхода читают слова буква за буквой, но в разном порядке. При просмотре по столбцам работа останавливается при первом расхождении.

Сокращайте префикс слово за словом

Идея

Предположим, что ответом является первое слово целиком. Сократите его до части, общей со вторым словом, затем с третьим и так далее. Общий префикс нескольких слов — это общий префикс первых двух слов, затем этого префикса и третьего слова: на каждом шаге его можно только сохранить или укоротить. Например, в примере 1 кандидат меняется с interview на inter после второго слова и остаётся таким.

Каждая буква сравнивается не более одного раза, поэтому время работы составляет O(S), где S — общее количество букв. Слабое место — порядок: если есть 200 слов по 200 букв, и только последнее слово отличается первой буквой, до того как последнее слово сократит префикс до пустой строки, будет выполнено почти 40 000 сравнений.

Алгоритм

Задай prefixLen равным длине strs[0].
Для каждого другого слова посчитай, сколько начальных букв у него совпадает с strs[0], но не больше prefixLen.
Задай prefixLen равным этому количеству и остановись раньше, если оно достигнет 0.
Верни первые prefixLen букв из strs[0].

def longestCommonPrefix(strs):
    first = strs[0]
    prefix_len = len(first)
    for word in strs[1:]:
        common = 0
        while common < prefix_len and common < len(word) and word[common] == first[common]:
            common += 1
        prefix_len = common
        if prefix_len == 0:
            break
    return first[:prefix_len]

Сравнивайте по столбцам

Идея

Читайте слова как таблицу, по одному столбцу за раз. Возьмите букву из strs[0] в текущем столбце и проверьте, что в этом столбце она совпадает у всех остальных слов. При первом несовпадении или если слово слишком короткое, чтобы содержать этот столбец, ответом будет strs[0] до этого столбца.

Ответ — это ровно последовательность столбцов, в которых буквы всех слов совпадают, а этот цикл проходит эту последовательность слева направо и останавливается там, где совпадение нарушается. Если совпадение не нарушается, ответом будет strs[0].

Для n слов и ответа длины L цикл выполняет не более n × (L+1) проверок, что также равно O(S). Если из 200 слов отличается только последнее, причём его первая буква отличается, цикл остановится после 199 сравнений.

Алгоритм

Пусть first будет равен strs[0].
Для каждого столбца col от 0 до длины first минус один прочитай first[col].
Для каждого другого слова, если в нём нет буквы в позиции col или эта буква отличается, верни первые col букв из first.
Если все столбцы совпадают, верни first.

def longestCommonPrefix(strs):
    first = strs[0]
    for col in range(len(first)):
        for word in strs[1:]:
            if col == len(word) or word[col] != first[col]:
                return first[:col]
    return first

Ловушки и крайние случаи

Чтение за концом более короткого слова. В prefix, pre, prepare столбец 3 есть в prefix, но отсутствует в pre; перед чтением буквы проверь длину.
Сравнение только первого и последнего слова без сортировки. В abc, xbd, abd эти два слова имеют общий префикс ab, но xbd нарушает совпадение в столбце 0, поэтому ответ — пустая строка.
Возврат null или заполнителя, если ничего не совпадает. Ответ — пустая строка.
Забывая, что одно слово является собственным префиксом: если дано только algorithm, результатом будет algorithm.
Добавление по одной букве к неизменяемой строке. Ответ длиной 200 букв потребует 200 копирований; храни длину, а затем один раз вырежи часть первого слова.

Частые вопросы4

Какова временная сложность алгоритма поиска наибольшего общего префикса?

Оба прохода выполняются за время O(S), где S — общее количество букв, и используют O(1) дополнительной памяти помимо ответа. Проход по столбцам также ограничен величиной n × (L+1) для ответа длины L, поэтому он останавливается раньше, если слова расходятся ближе к началу.

Сможешь ли ты найти самый длинный общий префикс, отсортировав слова?

Да. В алфавитном порядке каждое слово между первым и последним начинается с того, что есть в начале у обоих, поэтому для получения ответа достаточно сравнить только эти два слова. Сортировка сравнивает примерно n log n пар слов, что требует больше затрат, чем один проход, но код короткий.

Что должна возвращать Longest Common Prefix, если общего префикса нет?

Пустая строка "". Это происходит, как только два слова начинаются с разных букв, как в stack, queue и heap.

Что лучше: горизонтальное или вертикальное сканирование?

У обоих алгоритмов одинаковая худшая временная сложность — O(S). Вертикальное сканирование — более безопасный выбор: оно останавливается на первом столбце, где какое-либо слово не совпадает, тогда как при горизонтальном сканировании длинный префикс может сравниваться со многими словами, прежде чем несовпадение в более позднем слове прервёт сравнение.

def longestCommonPrefix(strs):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

strs = ["interview", "internet", "interval", "internal"]

Ожидаемый вывод

"inter"