정규식 일치

입력 문자열s 및 패턴p이 주어지면 '.' 및 '*'를 지원하는 정규식 일치를 구현합니다.

'.' 모든 단일 문자와 일치합니다.

'*' 0개 이상의 이전 요소와 일치합니다.

일치는 전체 입력 문자열(부분이 아님)을 포함해야 합니다.

예 1:

입력: s = "aa", p = "a"
출력: 거짓
설명: "a"는 전체 문자열 "aa"와 일치하지 않습니다.

예 2:

입력: s = "aa", p = "a*"
출력: 참
설명: '*'는 선행 요소 'a'가 0개 이상 있음을 의미합니다. 따라서 'a'를 한 번 반복하면 'aa'가 됩니다.

예 3:

입력: s = "ab", p = ".*"
출력: 참
설명: ".*"는 "모든 문자(.)의 0개 이상(*)"을 의미합니다.

제약:

1 <= s.length <= 20

1 <= p.length <= 30

s에는 영문 소문자만 포함되어 있습니다.

p에는 소문자 영문자, '.' 및 '*'만 포함됩니다.

캐릭터가 나타날 때마다 보장됩니다'*'. 일치시킬 이전 유효한 캐릭터가 있습니다.

해결책:

class Solution:
    def isSame(self, a, b):
        if a == "." or b == ".":
            return True
        return a == b

    def isMatchRec(self, s, p, i, j, m, n):
        if i >= m:
            if j >= n:
                return True
            return j < n - 1 and p[j + 1] == "*" and self.isMatchRec(s, p, i, j + 2, m, n)
        if j >= n:
            return i >= m
        if j == n - 1 or p[j + 1] != "*":
            return self.isSame(s[i], p[j]) and self.isMatchRec(s, p, i + 1, j + 1, m, n)
        if p[j + 1] == "*":
            return self.isMatchRec(s, p, i, j + 2, m, n) or (self.isSame(s[i], p[j]) and self.isMatchRec(s, p, i + 1, j, m, n))
        return False

    def isMatch(self, s: str, p: str) -> bool:
        m = len(s)
        n = len(p)
        return self.isMatchRec(s, p, 0, 0, m, n)