[Leetcode] 10. Regular Expression Matching

문제 바로가기

반복문으로 푼다고 온갖 경우들을 다 생각하면서 짜다가 너무 시간이 오래 걸려서 포기했다.
같은 상황이 반복되면 recursion으로 푸는 것을 고려하자!

Recursion

Kleene stars를 만나는 경우와 아닌 경우를 기점으로 나눠가면서 회귀함수로 해결할 수 있다.

class Solution:
    def isMatch(self, text: str, pattern: str) -> bool:
        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(text, pattern[2:]) or
                    first_match and self.isMatch(text[1:], pattern))
        else:
            return first_match and self.isMatch(text[1:], pattern[1:])

Recursion + DP

Top-Down Variation

class Solution:
    def isMatch(self, text: str, pattern: str) -> bool:
        memory = {}

        def dp(idxT, idxP):
            if (idxT, idxP) not in memory:
                if idxP == len(pattern):
                    answer = idxT == len(text)
                else:
                    first_match = idxT < len(text) and pattern[idxP] in { text[idxT], '.' }

                    if idxP + 1 < len(pattern) and pattern[idxP + 1] == '*':
                        answer = dp(idxT, idxP + 2) or (first_match and dp(idxT + 1, idxP))
                    else:
                        answer = first_match and dp(idxT + 1, idxP + 1)
                memory[idxT, idxP] = answer
            return memory[idxT, idxP]

        return dp(0, 0)

Bottom-Up Variation

class Solution:
    def isMatch(self, text: str, pattern: str) -> bool:
        dp = [[False] * (len(pattern) + 1) for _ in range(len(text) + 1)]

        dp[-1][-1] = True
        for idxT in range(len(text), -1, -1):
            for idxP in range(len(pattern) - 1, -1, -1):
                first_match = idxT < len(text) and pattern[idxP] in {text[idxT], '.'}
                if idxP+1 < len(pattern) and pattern[idxP+1] == '*':
                    dp[idxT][idxP] = dp[idxT][idxP+2] or first_match and dp[idxT+1][idxP]
                else:
                    dp[idxT][idxP] = first_match and dp[idxT+1][idxP+1]

        return dp[0][0]