Пример решения задачи #14. Python LeetCode, Longest Common Prefix

Вариант решения задачи на языке программирования Python с LeetCode.
Категория: Алгоритмы.
Название задачи: Longest Common Prefix.
Сложность: Легкая.
Статус решения: "Решено".

Условие задачи:
Напишите функцию для нахождения самой длинной общей префиксной строки среди массива строк. Если общего префикса нет, верните пустую строку "".

Решение:

Python

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        # Если входной список пуст, возвращаем пустую строку
        if not strs:
            return ""
        
        # Берем первый элемент списка как начальный префикс
        prefix = strs[0]
        
        # Проходим по всем остальным строкам в списке
        for s in strs[1:]:
            # Сокращаем префикс до тех пор, пока он не станет префиксом текущей строки
            while not s.startswith(prefix):
                # Уменьшаем длину префикса на один символ с конца
                prefix = prefix[:-1]
                # Если префикс стал пустым, возвращаем пустую строку (нет общего префикса)
                if not prefix:
                    return ""
        
        # Возвращаем общий префикс
        return prefix

Объяснение кода

Проверка на пустой список:
В самом начале мы проверяем, является ли входной список strs пустым. Если это так, то сразу возвращаем пустую строку, так как нет строк для сравнения.

Инициализация префикса:
Мы предполагаем, что первый элемент списка (strs[0]) является общим префиксом. Это отправная точка для дальнейших сравнений.

Итерация по оставшимся строкам:
Начиная со второй строки (индекс 1), мы проходим по всем строкам в списке.
Для каждой строки мы проверяем, начинается ли она с текущего значения переменной prefix. Если нет, уменьшаем длину префикса на один символ с конца и снова проверяем.

Сокращение префикса:
Если текущая строка не начинается с текущего префикса, мы последовательно укорачиваем его (prefix = prefix[:-1]), пока он не станет префиксом текущей строки или пока не станет пустым.

Возврат результата:
После завершения цикла переменная prefix будет содержать самый длинный общий префикс всех строк в списке. Если общий префикс отсутствует, функция вернет пустую строку.

Пример работы программы:
strs = ["flower", "flow", "flight"]
solution = Solution()
print(solution.longestCommonPrefix(strs)) # Output: "fl"

Источник решения: hdhai.com