LeetCode: 10. Regular Expression Matching

여러 경우의 수를 다 고려해봐야 한다.

어려운 문제이긴하나, dp를 써야한다는 점과 dp table의 크기를 정하는 것이 핵심.

여기서 matched[i][j]: p[i-1]까지의 패턴 문자열이 s[j-1] 문자열을 cover함을 의미.

class Solution(object):
    def isMatch(self, s, p):
        matched = [[False] * (len(s)+1) for _ in range(len(p)+1)]
        matched[0][0] = True
        
        for i in range(2, len(p)+1):
            if p[i-1] == '*':
                matched[i][0] = matched[i-2][0]
        
        for i in range(1, len(p)+1):
            for j in range(1, len(s)+1):
                if p[i-1] == '.':
                    matched[i][j] = matched[i-1][j-1]
                elif p[i-1] == '*':
                    if p[i-2] == '.':
                        matched[i][j] = matched[i-2][j] or matched[i-1][j] or \
                        matched[i][j-1]
                    else:
                        matched[i][j] = matched[i-2][j] or matched[i-1][j] or \
                        (matched[i][j-1] and p[i-2] == s[j-1])
                else:
                    matched[i][j] = matched[i-1][j-1] and (p[i-1] == s[j-1])
        return matched[len(p)][len(s)]