[leetcode 매일 풀기] 10. regular expression matching

오늘 정리할 문제는 leetcode 알고리즘의 10번 문제 regular expression matching이라는 문제이다.

 

https://leetcode.com/problems/regular-expression-matching/submissions/1105739483/

LeetCode - The World's Leading Online Programming Learning Platform

 

간략화된 pattern (특수기호는 2가지 ".": 어떤 single character와도 매치가능,  "*": 0이상의 아무 character와 매치가능)과 string이 있을때. pattern을 만족하는 string이 있는지 체크하라는 코드이다.

 

맨처음에는 아래와 같이 회귀함수를 작성해서 가능한 모든 경우를 체크하는 코드를 작성했다.

test code에서는 잘 작동하길래 제출해보았는데

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if len(s) == 0 and len(p) == 0:
            return True
        elif len(p) == 0:
            return False

        if len(p) > 1 and p[1] == "*":
            if self.isMatch(s, p[2:]):
                return True
            for index in range(len(s)):
                if s[index] == p[0] or p[0] == ".":
                    if self.isMatch(s[index + 1 :], p[2:]):
                        return True
                else:
                    break
        elif len(s) > 0:
            if s[0] == p[0] or p[0] == ".":
                return self.isMatch(s[1:], p[1:])

        return False

 

이게 웬걸 Time limit이 뜨는걸 확인하고. 뭐지하고 solution 탭에 들어가서 다른사람들의 풀이를 확인

 

풀이를 보니 Dynamic Programming을 이용해서 중간 결과물을 저장해서 빠르게 return하는 일을 해서, 아래와 같이 코드를 작성해서 통과시켰다.

class Solution:
    memo = None
    s = None
    p = None

    def isMatch(self, s: str, p: str) -> bool:
        self.memo = {}
        self.s = s
        self.p = p
        return self.dp(0, 0)

    def dp(self, i, j):
        key = (i, j)
        if key in self.memo:
            return self.memo[key]

        if i == len(self.s) and j == len(self.p):
            return True
        elif j == len(self.p):
            return False

        if j + 1 < len(self.p) and self.p[j + 1] == "*":
            if self.dp(i, j + 2):
                self.memo[key] = True
                return self.memo[key]

            if i < len(self.s):
                if self.s[i] == self.p[j] or self.p[j] == ".":
                    if self.dp(i + 1, j):
                        self.memo[key] = True
                        return self.memo[key]
        elif i < len(self.s):
            if self.s[i] == self.p[j] or self.p[j] == ".":
                self.memo[key] = self.dp(i + 1, j + 1)
                return self.memo[key]
        self.memo[key] = False

        return self.memo[key]


assert Solution().isMatch("aa", "a") is False
assert Solution().isMatch("aa", "a*") is True
assert Solution().isMatch("ab", ".*") is True
assert Solution().isMatch("mississippi", "mis*is*p*.") is False
assert Solution().isMatch("a", "ab*") is True
assert Solution().isMatch("a", ".*..a*") is False

 

 

 

다른사람들의 solution을 보니 더 짧게 잘 작성한 것도 보이고, 내 코드를 개선하는데 도움이 되는 아이디어를 받을 수 있다.

 

1. 앞으로도 꾸준히 solution을 만든다음 다른 사람들 solution을 보고 개선점을 생각해보면 좋겠고

2. 반복되는 iteration을 할 수 있는 결과는 dp로 푸는 사고를 잊지 말아야겠다.