Given an input string (s) and a pattern §, implement regular expression matching with support for ‘.’ and ‘*’.

  1. ‘.’ Matches any single character.
  2. ‘*’ Matches zero or more of the preceding element.
    The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

这道题跟Wildcard Matching是类似的,可以用动态规划算法求解,只不过这里的*只能匹配0个或者多个s[i]前面的字符。
同样,我们定义二维数组dp,其中dp[i][j]表示s[0,i)和p[0,j)是否match。现在求解dp[i+1][j+1]的值:(查看s[i]和p[j])

  1. 如果p[j] == ‘*’, 并且匹配s[i-1]0次,则

    dp[i+1][j+1] = dp[i][j-1];
  2. 如果p[j] == ‘*’, 并且匹配重复s[i-1]多次,则,

    在条件 s[i] == p[j-1] || p[j-1] == ‘.’ 成立的情况下

    dp[i+1][j+1] = dp[i-1][j];
  3. 如果p[j] != ‘*’,在(s[i] == p[j ] || p[j] == ‘.’)成立的情况下

    dp[i+1][j+1] = dp[i-1][j-1];