Общий префикс строк

Решение: Поиск Общего Префикса Строк

Эта задача требует найти самый длинный общий префикс в массиве строк — подстроку, с которой начинаются все строки в массиве.

Подход 1: Горизонтальное Сравнение (Простой способ)

Сравниваем первую строку со всеми остальными, поэтапно укорачивая префикс:

def longest_common_prefix(strs: list[str]) -> str:
    if not strs:
        return ""
    
    prefix = strs[0]
    
    for string in strs[1:]:
        while not string.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    
    return prefix

Сложность:

• Временная: O(m * n), где m — длина самой короткой строки, n — количество строк
• Пространственная: O(1)

Подход 2: Вертикальное Сравнение (Более Эффективный)

Сравниваем символы по позициям. На каждой позиции проверяем все строки:

def longest_common_prefix(strs: list[str]) -> str:
    if not strs:
        return ""
    
    for i in range(len(strs[0])):
        char = strs[0][i]
        
        for j in range(1, len(strs)):
            if i >= len(strs[j]) or strs[j][i] != char:
                return strs[0][:i]
    
    return strs[0]

Сложность: O(m * n), но выходит раньше при первом несовпадении

Подход 3: Разделяй и Властвуй

Рекурсивно делим массив пополам и ищем префикс каждой половины:

def longest_common_prefix(strs: list[str]) -> str:
    def find_prefix(left, right):
        if left == right:
            return strs[left]
        
        mid = (left + right) // 2
        left_prefix = find_prefix(left, mid)
        right_prefix = find_prefix(mid + 1, right)
        
        i = 0
        while i < len(left_prefix) and i < len(right_prefix) and left_prefix[i] == right_prefix[i]:
            i += 1
        
        return left_prefix[:i]
    
    if not strs:
        return ""
    
    return find_prefix(0, len(strs) - 1)

Сложность: O(m * n) худший случай, но лучше на среднем случае

Примеры

print(longest_common_prefix(["дом", "домен", "домра", "доширак"]))  # → "до"
print(longest_common_prefix(["dog", "racecar", "car"]))  # → ""
print(longest_common_prefix(["abc"]))  # → "abc"
print(longest_common_prefix([]))  # → ""
print(longest_common_prefix(["a", "a", "a"]))  # → "a"

Рекомендация

Для собеседования используй подход 1 (горизонтальное сравнение) — он самый простой и понятный. Если собеседующий попросит оптимизацию, предложи вертикальное сравнение с ранним выходом.