19. 正则表达式匹配

动态规划https://leetcode-cn.com/problems/regular-expression-matching/solution/dong-tai-gui-hua-zen-yao-cong-0kai-shi-si-kao-da-b/

• 如果 p.charAt ( j ) == s.charAt ( i ) : dp[i][j] = dp[i-1][j-1]；
• 如果 p.charAt ( j ) == '.' : dp[i][j] = dp[i-1][j-1]；
• 如果 p.charAt ( j ) == '*'：
  1. 如果 p.charAt ( j - 1 ) != s.charAt ( i ) : dp[i][j] = dp[i][j-2] //in this case, a* only counts as empty，e.g.b&ba*
  2. 如果 p.charAt ( j - 1 ) == s.charAt ( i ) or p.charAt (j-1) == '.'：
     1. dp [i] [j] = dp [i-1] [j] //in this case, a* counts as multiple a , e.g.baaa&ba*
     2. or dp [i] [j] = dp [i] [j-1] // in this case, a* counts as single a, e.g.ba&ba*(注意这个条件可以忽略，它等价于dp [i-1] [j] = dp [i-1] [j-2] 的情形，即b&ba*)
     3. or dp [i] [j] = dp [i] [j-2] // in this case, a* counts as empty, e.g.ba&baa*

class Solution:
    # s, pattern都是字符串
    def match(self, s, pattern):
        # write code here
        ls, lp = len(s), len(pattern)
        dp = [[False for _ in range(lp + 1)] for _ in range(ls + 1)]
        dp[0][0] = True
        for i in range(1, lp + 1):
            if i - 2 >= 0 and pattern[i - 1] == '*':
                dp[0][i] = dp[0][i - 2]
        for i in range(1, ls + 1):
            for j in range(1, lp + 1):
                m, n = i - 1, j - 1
                if pattern[n] == '*':
                    if s[m] == pattern[n - 1] or pattern[n - 1] == '.':
                        dp[i][j] = dp[i][j - 2] or dp[i - 1][j]
                    else: dp[i][j] = dp[i][j - 2]
                elif s[m] == pattern[n] or pattern[n] == '.':
                    dp[i][j] = dp[i - 1][j - 1]
        return dp[-1][-1]