Longest Common Prefix: четыре подхода и какой называть на собеседовании

Коротко

Обозначения: $n$ — число строк, $S$ — сумма их длин, $m$ — длина самой короткой, $\ell$ — длина самой длинной, $k$ — длина ответа.

• Пишите вертикальный проход: он простой, не требует памяти и не читает лишнего.
• Сортировку и бинарный поиск назовите как альтернативы и объясните, почему они хуже.
• Для исходной задачи бор избыточен. Он нужен, когда запросы идут по части набора, а сам набор меняется или запрос идёт посимвольно.

Задача

Дан массив строк, нужно найти самую длинную строку, с которой начинаются все элементы. Если такой нет, вернуть пустую.

["flower", "flow", "flight"]                   -> "fl"
["interspecies", "interstellar", "interstate"] -> "inters"
["dog", "racecar", "car"]                      -> ""

Это задача №14 на LeetCode с уровнем Easy. Такие обычно дают на разминке или техническом скрининге, поэтому оценивают не саму идею, а аккуратность: границы, пустые строки и честную оценку сложности.

Не путайте её с соседями. Наибольшая общая подпоследовательность — это уже динамика, а массив LCP из суффиксного массива хранит общие префиксы соседних суффиксов одной строки.

Перед кодом задайте два вопроса. Может ли массив быть пустым? На LeetCode и в задаче на нашем сайте в нём минимум одна строка, но в живом разговоре это стоит проговорить. Какой алфавит? От него зависит, можно ли спокойно сравнивать по символам (об этом в разделе про ошибки).

Вертикальный проход

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

индекс   0 1 2 3 4 5
flower   f l o w e r
flow     f l o w
flight   f l i g h t
             ^ столбец 2: o != i, ответ — первые два символа

def lcp_vertical(strs: list[str]) -> str:
    first = strs[0]
    for i, ch in enumerate(first):
        for s in strs:
            if i == len(s) or s[i] != ch:
                return first[:i]
    return first

Проверка i == len(s) закрывает случай ["flower", "flow"]: без неё получите IndexError на пятом столбце. Сравнение первой строки с самой собой лишнее, но безвредное. Зато не нужен strs[1:], который копировал бы список на каждом столбце.

Сложность. Полных столбцов $k$, в каждом $n$ сравнений, плюс один неполный столбец. Итого $O(n \cdot (k + 1))$. Обычно пишут $O(S)$, и это верная верхняя граница, но формула с $k$ показывает главное достоинство: хвосты строк алгоритм не читает. На ["a" * 10**6, "a" * 10**6, "b"] он сделает три сравнения.

На Python то же самое можно записать через zip. Он сам остановится на самой короткой строке, поэтому отдельная проверка границ не нужна:

def lcp_zip(strs: list[str]) -> str:
    result = []
    for column in zip(*strs):
        if len(set(column)) > 1:
            break
        result.append(column[0])
    return ''.join(result)

Код хороший, но на собеседовании сначала напишите версию с индексами. В ней видно, что вы понимаете, где граница. Вариант с zip покажите после.

Горизонтальное сужение

Идея опирается на тождество: общий префикс трёх строк равен общему префиксу первых двух, сравнённому с третьей.

$\mathrm{LCP}(a, b, c) = \mathrm{LCP}(\mathrm{LCP}(a, b), c)$

Держим кандидата и укорачиваем его, сверяя с каждой следующей строкой: flower → flow → fl.

Короткий вариант, который не O(S)

В разборах чаще всего встречается такой код:

def lcp_shrink(strs: list[str]) -> str:
    prefix = strs[0]
    for s in strs:
        while not s.startswith(prefix):
            prefix = prefix[:-1]
    return prefix

Он правильный, и при длинах до 200 символов, как на LeetCode, проблем не будет. Но его часто оценивают как $O(S)$, а это неверно. Каждая неудачная итерация копирует префикс и заново сравнивает его со строкой. На ["a" * L, "b"] получается $L$ итераций по $O(L)$ каждая, то есть квадрат от длины при сумме длин $L + 1$. Честная оценка — $O(S + L^2)$, где $L$ — длина первой строки.

Если срезы не копируют данные (как в Go), всё равно остаётся повторное сравнение. На двух строках "a" * L и "a" * (L // 2) + "b" * (L // 2) каждая проверка пройдёт $L/2$ символов и упадёт, и таких проверок тоже $L/2$.

Линейный вариант

Лечится это одним указателем: длину общей части двух строк находим за один проход.

def common_prefix(a: str, b: str) -> str:
    limit = min(len(a), len(b))
    i = 0
    while i < limit and a[i] == b[i]:
        i += 1
    return a[:i]


def lcp_horizontal(strs) -> str:
    it = iter(strs)
    prefix = next(it, '')
    for s in it:
        prefix = common_prefix(prefix, s)
        if not prefix:
            break
    return prefix

Сложность. Каждый вызов common_prefix читает не больше символов, чем есть в текущей строке, поэтому в сумме $O(S)$.

В отличие от вертикального прохода, этот вариант зависит от порядка строк. На ["a" * 10**6, "a" * 10**6, "b"] он честно сравнит миллион символов, а если поставить "b" первой, остановится сразу.

Зато у него есть своя ниша. Функция принимает любой итерируемый объект и держит в памяти только текущий префикс. Если строки лежат в большом файле и читаются построчно, вертикальный проход не подойдёт: ему нужны все строки сразу.

То же тождество работает и для распределённого счёта: каждая машина считает префикс своей части, а результаты объединяются через common_prefix. По этой же схеме устроен вариант «разделяй и властвуй», который тоже даёт $O(S)$.

Сортировка: первая и последняя строка

После лексикографической сортировки достаточно сравнить только крайние строки.

def lcp_sort(strs: list[str]) -> str:
    ordered = sorted(strs)
    return common_prefix(ordered[0], ordered[-1])

sorted(["flower", "flow", "flight"]) даёт ["flight", "flow", "flower"]. Общая часть flight и flower — это fl, и ответ совпадает. Строку посередине можно не смотреть.

Почему это работает. Пусть $a$ и $b$ — минимальная и максимальная строки, а $p$ — их общий префикс. Возьмём любую строку $s$ и предположим, что она не начинается с $p$. Посмотрим на первую позицию, где она расходится с $p$:

• $s$ там меньше символа из $p$ или уже закончилась. Тогда $s < a$, потому что $a$ начинается с $p$.
• $s$ там больше. Тогда $s > b$ по той же причине.

Оба случая противоречат тому, что $a$ минимальна, а $b$ максимальна. Значит, $p$ есть у всех. Длиннее он быть не может, потому что сразу за ним $a$ и $b$ расходятся.

Сложность. Одно сравнение строк стоит до $\ell$ символов, сравнений $O(n \log n)$. Итого $O(\ell \cdot n \log n)$ и $O(n)$ памяти. Формула без $\ell$ — типичная ошибка: «сортировка, значит $O(n \log n)$» здесь неверно.

Сортировка не нужна

В доказательстве упорядоченность использована только для того, чтобы получить минимум и максимум. Их можно найти одним проходом:

def lcp_minmax(strs: list[str]) -> str:
    return common_prefix(min(strs), max(strs))

Это $O(S)$ по времени, $O(1)$ по памяти и одна строка кода. Хороший ход на собеседовании: написать сортировку и тут же заметить, что порядок целиком не нужен. Кстати, min и max можно вести и на потоке строк.

Так же устроена os.path.commonprefix из стандартной библиотеки Python. Для путей она не годится, потому что работает посимвольно: для /usr/lib и /usr/local вернёт /usr/l. В документации Python 3.15 функция помечена как устаревшая, а для путей рекомендована os.path.commonpath.

Ловушка с порядком

Доказательство работает только для посимвольного порядка. Как только сортировка учитывает регистр или локаль, приём ломается:

const pair = (a, b) => {
  let i = 0
  while (i < a.length && i < b.length && a[i] === b[i]) i++
  return a.slice(0, i)
}

const words = ['Ab', 'aa', 'ac']

const plain = [...words].sort()
console.log(JSON.stringify(pair(plain[0], plain.at(-1)))) // ""

const local = [...words].sort((a, b) => a.localeCompare(b))
console.log(JSON.stringify(pair(local[0], local.at(-1)))) // "a" — неверно

У Ab и aa общего префикса нет, но localeCompare поставит Ab посередине, и его никто не проверит. То же случится в Python с sorted(strs, key=str.lower).

Бинарный поиск по длине

Заметим монотонность: если все строки начинаются с префикса длины $x$, то и с любого более короткого тоже. Значит, по длине ответа можно искать бинарным поиском. Это обычный бинарный поиск по ответу.

def lcp_binary(strs: list[str]) -> str:
    shortest = min(strs, key=len)
    lo, hi = 0, len(shortest)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        candidate = shortest[:mid]
        if all(s.startswith(candidate) for s in strs):
            lo = mid
        else:
            hi = mid - 1
    return shortest[:lo]

Округление вверх в mid обязательно. Иначе при lo = 0, hi = 1 получится mid = 0, ветка lo = mid ничего не изменит, и цикл не закончится. Подробнее об этой ошибке — в статье про бинарный поиск.

Разбор на ["flower", "flow", "flight"], самая короткая строка — flow:

Сложность. Шагов $O(\log m)$, каждая проверка стоит до $n \cdot m$. Итого $O(n \cdot m \log m)$, что в худшем случае хуже вертикального прохода на множитель $\log m$.

Логарифм здесь обманчив: он не заменяет линейный проход, а умножается на него. Если сказать «бинарный поиск быстрее, там же логарифм», это будет ошибкой.

Подход оправдан, только если одна проверка дешевле полного чтения. С префиксными хешами проверка одной строки стоит $O(1)$, и запрос по любому подмножеству из $t$ строк обходится в $O(t \log m)$ вместо $O(t \cdot k)$. Цена — предподсчёт, память и риск коллизий. Ещё один случай: вопрос «у всех ли есть такой префикс?» отправляется во внешнюю систему, и число таких запросов важнее числа символов.

Что показывают замеры

Я прогнал все варианты на ноутбуке с CPython 3.9. Смотрите на порядки, а не на точные цифры.

Здесь видно три вещи.

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

Третья строка показывает цену квадрата. Короткий вариант со startswith выглядит лучшим в первой строке, а в третьей работает секунды.

Первая строка — про константы, а не про алгоритмы. Бинарный поиск в CPython обгоняет вертикальный проход примерно в 80 раз, потому что startswith выполняется на C, а вложенный цикл — в интерпретаторе. Это особенность языка. В Node на тех же данных всё наоборот: вертикальный проход занял 12 мс, бинарный поиск — 43 мс.

Если интервьюер спросит про реальную скорость на Python, эта оговорка будет плюсом. Но сложность от неё не меняется.

Какой называть на собеседовании

Порядок разговора на пять минут:

1. Уточните, может ли массив быть пустым и какой алфавит.
2. Напишите вертикальный проход и проговорите границу i == len(s).
3. Назовите сложность: $O(n \cdot (k + 1))$, в худшем случае $O(S)$, дополнительной памяти нет. Быстрее $O(S)$ в худшем случае не выйдет: если все строки одинаковые, прочитать надо каждый символ.
4. Прогоните глазами ["flower", "flow"] и [""].
5. Скажите про альтернативы: сортировку можно заменить на min и max, а бинарный поиск по длине здесь ничего не выигрывает.

Дальше обычно идут вопросы на развитие. Заготовьте ответы:

Когда нужен бор

Бор часто называют сразу, как только в условии появляется слово «префикс». Для исходной задачи это лишнее. Слова складываются в префиксное дерево, ответ находится спуском от корня, пока у узла один потомок и он не конец слова. Время то же $O(S)$, но памяти уходит гораздо больше.

Я замерил 100 тысяч случайных слов из 10 букв: сами строки заняли около 7 МБ, бор с __slots__ — около 180 МБ. Случайные слова для бора неудобны, общих начал у них мало, но порядок разницы показательный.

Популярный довод «а если запросов $q$ будет много, нужен бор» тоже не работает. Из тождества выше следует, что $\mathrm{LCP}(S \cup \{q\}) = \mathrm{LCP}(\mathrm{LCP}(S), q)$. Префикс набора считается один раз и хранится как одна строка, а запрос стоит $O(\min(|q|, k))$:

base = lcp_vertical(['flower', 'flow', 'flight'])
common_prefix(base, 'flask')  # 'fl'

Бор начинает окупаться, когда запрос касается не всего набора, а его части. Классический пример — автодополнение по Tab: пользователь набрал начало, и надо дописать всё, что общее у подходящих слов.

class Node:
    __slots__ = ('children', 'is_end')

    def __init__(self) -> None:
        self.children = {}
        self.is_end = False


class Trie:
    def __init__(self) -> None:
        self.root = Node()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, Node())
        node.is_end = True

    def complete(self, prefix: str = '') -> str | None:
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None  # слов с таким началом нет
        result = [prefix]
        while len(node.children) == 1 and not node.is_end:
            ch, node = next(iter(node.children.items()))
            result.append(ch)
        return ''.join(result)


trie = Trie()
for word in ['commit', 'common', 'compare', 'config', 'conflict', 'connect']:
    trie.insert(word)

trie.complete()  # 'co'
trie.complete('comp')  # 'compare'
trie.complete('conf')  # 'conf'
trie.complete('x')  # None

Проверка not node.is_end здесь обязательна. Без неё в наборе flow, flower спуск прошёл бы до flower, хотя flow — тоже слово набора.

Но если набор не меняется, с этим справится и отсортированный массив. Диапазон слов с нужным началом находится бинарным поиском, а дальше работает знакомый приём с крайними строками:

from bisect import bisect_left


def complete_sorted(words: list[str], prefix: str = '') -> str | None:
    lo = bisect_left(words, prefix)
    hi = bisect_left(words, prefix + '\U0010ffff')
    if lo == hi:
        return None
    return common_prefix(words[lo], words[hi - 1])

Это $O(|p| \log n)$ на поиск диапазона и компактная память. Поэтому бор стоит брать, когда запросы идут по части набора и к этому добавляется хотя бы одно из двух:

• Набор часто меняется. Вставка в бор стоит $O(L)$, где $L$ — длина слова, а вставка в отсортированный массив сдвигает $O(n)$ элементов.
• Запрос надо вести посимвольно, продвигаясь вместе с вводом пользователя или текстом. Так работают автодополнение и поиск самого длинного совпадения в таблице маршрутов.

В остальных случаях хватит строки с префиксом или отсортированного массива. Если на собеседовании вы это проговорите, а не просто назовёте бор, получится сильнее.

Типичные ошибки

Нет проверки конца строки. В вертикальном проходе s[i] без i == len(s) падает на ["flower", "flow"]. Держите этот пример в голове как обязательный тест.

Неверная оценка. Самые частые промахи: $O(n)$ без учёта длин строк, $O(n \log n)$ для сортировки и $O(S)$ для варианта с startswith. Подробнее о том, как считать такие вещи, — в статье про О-большое.

Сортировка на месте. strs.sort() меняет входной массив. Если это не обговорено, используйте sorted(strs) или min и max.

Пустой массив. strs[0] бросит IndexError, min(strs) — ValueError. По условию пустого массива нет, но скажите об этом вслух.

Символы вне базовой плоскости в JavaScript. Строки там индексируются кодовыми единицами UTF-16, поэтому код выше разрежет эмодзи пополам:

const pair = (a, b) => {
  let i = 0
  while (i < a.length && i < b.length && a[i] === b[i]) i++
  return a.slice(0, i)
}

const broken = pair('😀', '😁')
console.log(broken.length, broken.codePointAt(0).toString(16)) // 1 d83d

const byCodePoint = (a, b) => {
  const x = [...a]
  const y = [...b]
  let i = 0
  while (i < x.length && i < y.length && x[i] === y[i]) i++
  return x.slice(0, i).join('')
}
console.log(JSON.stringify(byCodePoint('a😀', 'a😁'))) // "a"

В Python таких разрезов нет, он сравнивает кодовые точки. Но проблема комбинируемых символов остаётся и там: é в виде одного символа и в виде e плюс U+0301 не совпадут, пока строки не приведены к одной форме через unicodedata.normalize. Другие подводные камни разобраны в статье про задачи на строки.

Что запомнить

• Основной ответ — вертикальный проход: $O(n \cdot (k + 1))$, памяти нет, хвосты строк не читаются.
• Сужение через startswith и prefix[:-1] выглядит линейным, но в худшем случае квадратично. Нужен указатель.
• Горизонтальный проход хорош для потока и распределённого счёта: $\mathrm{LCP}$ можно объединять по частям.
• Сортировка работает благодаря лемме о крайних строках, но min и max дают тот же результат за $O(S)$. Порядок должен быть посимвольным, без localeCompare.
• Бинарный поиск по длине добавляет множитель $\log m$ и оправдан только при дешёвой проверке, например на хешах.
• Бор нужен для запросов по части набора, когда набор часто меняется или запрос идёт посимвольно. Для всего набора, даже при множестве запросов $q$, хватит одной строки с префиксом.