https://leetcode.com/problems/regular-expression-matching/
经典题目，考虑DP的多种情况。

个人解答

  1. class Solution:
  2.     def isMatch(self, s: str, p: str) -> bool:
  3.         @functools.lru_cache(None)
  4.         def match(si, pi):
  5.             if si == -1:
  6.                 # consider optional pattern
  7.                 while pi > 0 and p[pi] == '*':
  8.                     pi -= 2
  9.                 return pi == -1
  10.             if si < 0 or pi < 0:
  11.                 return False
  12.             if s[si] == p[pi] or p[pi] == '.':
  13.                 return match(si - 1, pi - 1)
  14.             if p[pi] == '*':
  15.                 if p[pi - 1] == s[si] or p[pi - 1] == '.':
  16.                     return match(si - 1, pi) or match(si, pi - 1) or match(si, pi - 2)
  17.                 else:
  18.                     return match(si, pi - 2)
  19.             return False
  21.         return match(len(s) - 1, len(p) - 1)

题目分析

https://leetcode.com/problems/regular-expression-matching/discuss/5651/Easy-DP-Java-Solution-with-detailed-Explanation
（上述解答里边有错误，关键的DP公式：

  1. 2   if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':

应该是：

  1. 2   if p.charAt(j-1) == s.charAt(i) or p.charAt(j-1) == '.':

这道题一开始不知道如何入手，想着parser那一套，似乎也不太行，后来看到DP的解法，豁然开朗。
其实就是，踏踏实实找状态，还是比较容易想到的。

分情况讨论：

  1. 最后一个字符相同（包括 . 的情况）： dp[si][pi] = dp[si - 1][pi - 1]
  2. 最后一个字符是 * ：
    1. 通配符前边的字符相同（包括 . 的情况），选择很多，可以要该字符0/1/2…次： dp[si][pi] = dp[si][pi - 2] or dp[si][pi - 1] or dp[si - 1][pi]
  3. 非法情况，return false

其中需要注意两点：

  1. 要通配符的字符2+次，关系是： dp[si][pi] = dp[si - 1][pi] ，还是要保留通配符，但是s前移了一位，这样递推下去就能做到通配2+次的效果
  2. 考虑pattern冗余的情况，比如到最后，s已经空了，但是p中还有 a*b* 这样的结构，此时需要消除掉