11. Longest Common Prefix

«Всякая хорошая программа должна быть понятна с первого взгляда, а любая сложная задача обязана сводиться к очевидной последовательности простых шагов».
— Брайан Керниган

LeetCode 14. Longest Common Prefix

Сложность: Easy
Тема: Массивы и строки, вертикальное сканирование, иммутабельность строк в Go
Ссылки: Теория: Массивы и строки, Типовые операции и приёмы, Valid Anagram

1. Введение и физическая интуиция

Представьте себе библиотеку или старинный архив, где на полке выставлены карточки с фамилиями авторов или инвентарными шифрами: "flower", "flow", "flight". Архивариус скользит пальцем слева направо по всем карточкам одновременно:

• Первая колонка: у всех 'f'? Да.
• Вторая колонка: у всех 'l'? Да.
• Третья колонка: у первой 'o', у второй 'o', у третьей 'i'. Стоп! Произошел рассинхрон. Общий префикс — "fl".

Это и есть вертикальное сканирование (vertical scanning).

Задача кажется элементарной, но именно на таких тестах проверяется зрелость инженера: понимание внутреннего устройства строк в Go (reflect.StringHeader), разницы между побайтовым доступом и декодированием UTF-8 рун, влияния слайсинга подстрок на Garbage Collector и умение выбрать алгоритм с оптимальным ранним выходом (early exit).

flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc

    A["strs: ['flower', 'flow', 'flight']"]:::entry --> B["Колонка 0: 'f' == 'f' == 'f' (OK)"]:::process
    B --> C["Колонка 1: 'l' == 'l' == 'l' (OK)"]:::process
    C --> D["Колонка 2: 'o' == 'o' != 'i' (Mismatch!)"]:::warning
    D --> E["Ранний выход: возвращаем first[:2] -> 'fl'"]:::success
  

2. Формулировка задачи и вопросы интервьюеру

Дана коллекция строк strs. Требуется найти самую длинную непустую строку, являющуюся общим префиксом для абсолютно всех строк массива. Если общего префикса нет — вернуть пустую строку "".

Вопросы интервьюеру (Senior-стиль):

1. Может ли массив быть пустым?
   «Да, len(strs) == 0. В этом случае сразу возвращаем пустую строку "".»
2. Может ли одна из строк быть пустой?
   «Да, если среди элементов есть "", максимальный общий префикс очевидно равен "".»
3. Каков алфавит?
   «В стандартной задаче LeetCode гарантируются строчные латинские буквы (ASCII, a–z). Если возможен произвольный UTF-8 (эмодзи, кириллица), нам потребуется итерироваться по границам рун, а не по сырым байтам.»
4. Регистрозависимость?
   «Да, 'A' != 'a'.»
5. Каков размер входных данных?
   «Обычно $N \le 200$, длина каждой строки $L \le 200$.»

3. Разбор подходов

Подход 1: Попарное горизонтальное сканирование (Наивный)

Берем первую строку как базовый префикс prefix = strs[0]. Затем по очереди берем каждую следующую строку s и укорачиваем prefix с конца, пока strings.HasPrefix(s, prefix) не станет true.

func longestCommonPrefixHorizontal(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    prefix := strs[0]
    for _, s := range strs[1:] {
        for len(prefix) > 0 && !strings.HasPrefix(s, prefix) {
            prefix = prefix[:len(prefix)-1]
        }
        if prefix == "" {
            return ""
        }
    }
    return prefix
}

Минусы:
Если в массиве первая строка очень длинная (скажем, 100 000 символов), а последняя строка начинается с совершенно другой буквы, горизонтальный метод сделает массу холостой работы, укорачивая префикс символ за символом для промежуточных строк. В худшем случае сложность стремится к $O(N \times L^2)$.

Подход 2: Вертикальное сканирование (Оптимальное)

Смотрим на массив строк как на двумерную символьную матрицу. Берем первый элемент strs[0] как эталон и идем по индексам колонок i:

• Проверяем символ strs[0][i] против символов s[i] во всех остальных строках.
• Как только наткнулись на конец любой строки (i == len(s)) или несовпадение символов (s[i] != strs[0][i]) — мы немедленно прекращаем работу и возвращаем strs[0][:i].

flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc

    A["first = strs[0]"]:::entry --> B["Внешний цикл: i от 0 до len(first)-1"]:::process
    B --> C["Внутренний цикл: строка s в strs[1:]"]:::process
    C --> D{"i >= len(s) ИЛИ s[i] != first[i]?"}:::warning
    D -->|"Да (Конец префикса)"| E["Вернуть first[:i]"]:::success
    D -->|"Нет"| F["Продолжить проверку строк"]:::process
    F --> C
    B --> G["Все строки совпали полностью"]:::process
    G --> H["Вернуть first целиком"]:::success
  

4. Эталонная реализация на Go

package main

// LongestCommonPrefix находит наибольший общий префикс массива строк
// методом вертикального сканирования колонок.
// Временная сложность: O(S), где S — сумма символов, просмотренных до первого несовпадения.
// Пространственная сложность: O(1) вспомогательной памяти.
func LongestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }

    first := strs[0]

    // Идем по колонкам первой строки-эталона
    for i := 0; i < len(first); i++ {
        char := first[i]

        // Сравниваем символ char с i-м символом каждой следующей строки
        for _, s := range strs[1:] {
            // Если строка s закончилась или символ на позиции i не совпал
            if i >= len(s) || s[i] != char {
                return first[:i]
            }
        }
    }

    // Если цикл завершился штатно, значит первая строка целиком входит во все остальные
    return first
}

5. Пошаговая трассировка (Walkthrough)

Возьмем входной массив strs = ["flower", "flow", "flight"].

Срабатывает ветка s[i] != char. Функция немедленно возвращает first[:2], то есть "fl". Никакие последующие символы строк даже не загружаются в регистры процессора.

6. Mechanical Sympathy: Strings, GC и кэши процессора

1. Срез строки first[:i] в Go:
   Строка в Go представлена 16-байтной структурой (в 64-битной архитектуре):

   Go Копировать

   type StringHeader struct {
       Data uintptr
       Len  int
   }
   

   Срез строки first[:i] не аллоцирует новый массив байтов в куче! Он лишь создает новый заголовок, поле Data которого указывает на тот же неизменяемый буфер в памяти, а Len равно i.

2. Кэш-локальность и Branch Predictor:
   Вертикальное сканирование прыгает по разным строкам на одном и том же смещении i. Однако при малом числе строк $N$ указатели на заголовки и первые кэш-линии строк отлично помещаются в L1/L2 кэш данных (L1d).

7. Работа с Unicode: когда сырых байт недостаточно

Если в ТЗ указано, что строки содержат произвольный UTF-8 (например, кириллицу или китайские иероглифы):

func longestCommonPrefixUnicode(strs []string) string {
    if len(strs) == 0 {
        return ""
    }

    firstRunes := []rune(strs[0])
    for i, r := range firstRunes {
        for _, s := range strs[1:] {
            sRunes := []rune(s)
            if i >= len(sRunes) || sRunes[i] != r {
                return string(firstRunes[:i])
            }
        }
    }
    return strs[0]
}

Замечание для интервьюера: Конвертация []rune(s) требует $O(L)$ времени и аллокации памяти в куче под массив int32. Для ASCII-диапазона побайтовое сканирование в разы быстрее и не требует аллокаций.

8. Вопросы для собеседования

9. Инварианты и чек-лист самопроверки

• [x] Пустой массив: проверка len(strs) == 0 предотвращает панику выхода за границы среза.
• [x] Массив из одного элемента: цикл по strs[1:] не выполнится, вернется вся строка first.
• [x] Пустая строка в середине: проверка i >= len(s) сработает на шаге i = 0 и безопасно вернет "".
• [x] Zero Allocations: для ASCII алгоритм не выполняет ни единой аллокации в куче (0 B/op).