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 — самое короткое слово, и два других начинаются с него, поэтому это и есть весь ответ. Общий префикс не может быть длиннее самого короткого слова.

+19 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

Идея

Начни с предположения, что всё первое слово и есть ответ. Затем сравни его со вторым словом побуквенно и сократи до общей части. Сравни то, что осталось, с третьим словом и так далее. После последнего слова останется то, что есть у всех слов.

Это верно, потому что общий префикс многих слов — это общий префикс первых двух слов, затем полученного результата и третьего слова и так далее: на каждом шаге его можно только сохранить или укоротить. Для interview, internet, interval, internal кандидат сокращается с interview до inter после второго слова и остаётся таким.

Каждая буква сравнивается не более одного раза, поэтому время работы составляет O(S), где S — общее количество букв. Ты хранишь только длину, а не копию. Слабое место этого подхода — порядок: если есть 200 слов по 200 букв, первые 199 слов совпадают, а последнее отличается уже первой буквой, то ты сравнишь все 200 букв с каждым из первых 199 слов — почти 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]

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

Идея

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

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

Цикл читает не более чем на один столбец дальше ответа, поэтому для n слов и ответа длиной L он выполняет не более n × (L+1) проверок и никогда не читает одну и ту же букву слова дважды, поэтому сложность также равна O(S). В приведённом выше случае, где 199 слов совпадают, а последнее отличается уже первой буквой, цикл останавливается после первого столбца: 199 сравнений вместо почти 40 000.

Алгоритм

Пусть 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). Вертикальное сканирование по столбцам — более безопасный выбор: оно останавливается на первом столбце, в котором слова различаются, тогда как при горизонтальном сканировании длинный префикс может сравниваться со многими словами, прежде чем одно из слов, стоящее ближе к концу, прервёт проверку.

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

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

Ожидается

"inter"