[leetcode] #10. Regular Expression Matching

문제 설명

링크
문자열이 정규식에 부합하는지 찾는 문제

접근 1 - Recursion

1. pattern 의 첫글자가 text의 첫글자와 같거나 '.' 이면 통과
2. pattern 에 '*' 문자가 있다면 ('*' 문자는 0번이상이므로)
   • *앞의 문자가 나타나지 않는 경우
   • *앞의 문자가 1이상 나타나는 경우
3. 나머지 text와 pattern 확인

코드 - Recursion

def isMatch(self, text, pattern):
    if not pattern:
        return not text

    first_match = bool(text) and pattern[0] in {text[0], '.'}

    if len(pattern) >= 2 and pattern[1] == '*':
        return (self.isMatch(self, text, pattern[2:]) or first_match and self.isMatch(self, text[1:], pattern))
    else:
        return first_match and self.isMatch(self, text[1:], pattern[1:])

접근 2 - 2차원 DP

0. s = ab, p = c*a*b* 일 때, 초기 배열 (s 가 빈 문자열일 때를 미리 초기화)

 // p ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
s [[1, 0, 1, 0, 1, 0, 1],
|  [0, 0, 0, 0, 0, 0, 0],
|  [0, 0, 0, 0, 0, 0, 0]]

1. pattern 의 글자가 s 와 같거나 '.' 문자일 경우, dp[i-1][j-1] 와 같음

   • 현재 문자에 대해서는 match 성립하고, 이전 문자와 이전 정규식까지에 달려 있는 것

2. patterh 의 글자가 * 라면

   • 해당 문자가 0번 나타남 = dp[i][j - 2] (해당 정규식의 문자 제외)

   • 해당 문자가 1번 이상 나타남 = *앞의 문자와 s 가 같거나 . 이고 이전 문자까지 성립

코드 - 2차원 DP

    def isMatch(self, s: str, p: str) -> bool:
        s, p = ' ' + s, ' ' + p
        lenS, lenP = len(s), len(p)
        dp = [[0] * (lenP) for i in range(lenS)]
        dp[0][0] = 1
 
        for j in range(1, lenP):
            if p[j] == '*':
                dp[0][j] = dp[0][j - 2]

        for i in range(1, lenS):
            for j in range(1, lenP):
                if p[j] in {s[i], '.'}:
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j] == "*":
                    dp[i][j] = dp[i][j - 2] or int(dp[i - 1][j] and p[j - 1] in {s[i], '.'})

        return bool(dp[-1][-1])