Пример решения задачи #10. Python LeetCode, Сопоставление регулярных выражений

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

Условие задачи:
Учитывая входную строку s и шаблон p, реализовать сопоставление регулярных выражений с поддержкой '.' и '*' где:

'.' Соответствует любому отдельному символу.
'*' Соответствует нулю или предыдущему элементу.

Решение:

Python

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        # Создаем двумерный массив для хранения результатов подзадач
        # dp[i][j] будет True, если первые i символов строки s совпадают с первыми j символами шаблона p
        dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]

        # Пустая строка совпадает с пустым шаблоном
        dp[0][0] = True

        # Заполняем случай, когда шаблон содержит '*', который может соответствовать пустой строке
        for j in range(1, len(p) + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]

        # Заполняем таблицу dp
        for i in range(1, len(s) + 1):
            for j in range(1, len(p) + 1):
                if p[j - 1] == '.' or p[j - 1] == s[i - 1]:
                    # Символы совпадают или шаблон содержит '.'
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':
                    # '*' может соответствовать нулю или более символам предыдущего элемента
                    dp[i][j] = dp[i][j - 2] or (dp[i - 1][j] and (p[j - 2] == s[i - 1] or p[j - 2] == '.'))

        # Возвращаем результат для всей строки и всего шаблона
        return dp[len(s)][len(p)]

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

Инициализация таблицы dp:
Создается двумерный массив dp размером (len(s)+1) x (len(p)+1). Каждая ячейка dp[i][j] представляет, совпадают ли первые i символов строки s с первыми j символами шаблона p.
dp[0][0] = True, так как пустая строка совпадает с пустым шаблоном.

Обработка шаблона с '' для пустой строки: Если символ шаблона равен '', он может соответствовать нулю вхождений предыдущего элемента. Это проверяется выражением dp[0][j] = dp[0][j-2].

Основная логика заполнения таблицы:
Если текущий символ шаблона p[j-1] равен '.' или совпадает с символом строки s[i-1], то dp[i][j] = dp[i-1][j-1].

Если текущий символ шаблона p[j-1] равен '*', возможны два случая:

1) '*' соответствует нулю вхождений предыдущего элемента: dp[i][j] = dp[i][j-2].

2) '*' соответствует одному или более вхождений предыдущего элемента: dp[i][j] = dp[i-1][j], если предыдущий символ шаблона (p[j-2]) равен текущему символу строки (s[i-1]) или равен '.'.

Результат:
Значение в ячейке dp[len(s)][len(p)] указывает, совпадают ли вся строка s и шаблон p.

Пример использования:
solution = Solution()
print(solution.isMatch("aa", "a")) # Ожидаемый результат: False
print(solution.isMatch("aa", "a")) # Ожидаемый результат: True print(solution.isMatch("ab", ".")) # Ожидаемый результат: True

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