10. Regular Expression Matching

问题

问题是说，我们有一个东西正则表达式（不知道什么是正则表达式不重要），他有一个pattern，可以匹配字符串。匹配的规则就是

1. 小写字母代表它本身
2. . 代表任意字符
3. * 代表他前面的字符可以匹配0次或者1次或者多次

举例来说就是我们有一个pattern a*, 我们可以匹配a, aa,aaaa,或者是空字符串。

给出一个字符串s，和一个pattern p，判断s是否可以匹配p。

解析

我会尽力还原每一步是如何想到的，将他们联系起来。

对于aaa是否匹配a*匹配问题，我们的思路一般是（可能我们有时候都不会注意到这个路径）：

• 首先看s中的第一个a是否匹配p中的第一个，不匹配则停止，匹配则继续看下一个字符;

• s的第二个字符a是否匹配p的第二个字符，对于p的第二个字符出现了*，我们需要回看p的第一个字符发现是a，那么基于前面的结果（s中的第一个a匹配p中的第一个a），而且当前第二步中，p中*的前一个字符是a，s的当前字符是a，也可以匹配；所以继续匹配

• s中的第三个a同第二部的匹配思路
• 最终结束匹配。

不知看到这里给予前面的结果一步步构建最终结果，是否可以联想到动态规划的最优子结构。如果可以想到，我们就按照动态规划的思路去构建代码了：

• 首先是看状态定义，根据结果长度为len(s)的字符是否匹配长度为len(p)，我们定义dp[m][n]。
• 然后转移公式：
  • 这里一开始我直接就按照最难的包含.和*的开始推导。根据题解的思路提示，可以先去思考没有星号的情况，就是只包含小写字母和点号。这个时候的话其实匹配的规则就很明朗，就是对应的字符匹配上，或者对应位置是一个点，那么也算匹配，就继续往下匹配即可，反之则结束。
  • 然后继续考虑加上星号的情况：
    • 如果遇到星号的话，存在几种情况：
      • s中的字符和星号之前的字符不相等
      • s中的字符和星号之前的字符相等
      • 星号之前的字符是.(也可以视为与当前s中的字符和星号之前的点相等)
    • 对于以上几种情况
      • 第一种，相当于当前的某个字符串c*匹配不上s中当前字符，此时我们dp[i][j]的结果需要基于dp[i][j-2]的结果（此处可以理解为j中这个字符以及星号没用了，匹配了0个字符）
      • 第二种以及第三种，可能匹配0次，或者一次，也可能匹配多次。匹配0次的话dp[i][j] = dp[i - 1][j - 2], 匹配一次的话dp[i][j] = dp[i - 1][j - 2],相当于说p中当前的字符匹配上了s中的*和他前一个字符（总共两个字符），所以是j - 2同第一种。匹配多次的话，我们可以考虑当前的结果是基于上一次的结果（aaa匹配a*基于aa匹配a*的基础），dp[i][j] = dp[i - 1][j],

• 然后初始化。

  • j和i都为0的时候，两个空字符串一定匹配，所以dp[0][0] = true;;

  • 当p的长度为0时候肯定除了上述的情况（空字符串），其他的都匹配不上，为默认值false；

  • 当s的长度为0的时候，能够匹配的pattern应该长得像a*a*b*c*...，所以当s长度为0，当前i位置, i - 1是星号，i的结果取决于i - 2的结果：

    java for (int i = 2; i < n + 1; i++) { if (p.charAt(j - 1) == '*' && dp[0][j - 2]) { dp[0][i] = true; } }

    可以确定一些偶数位。

代码

class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) return false;
        int m = s.length();
        int n = p.length();
        
        boolean[][] dp = new boolean[m + 1][n + 1];
        
        dp[0][0] = true;
        
        // initialization
        for (int i = 2; i < n + 1; i += 2) {
            if (p.charAt(i - 1) == '*' && dp[0][i - 2]) {
                dp[0][i] = true;
            }
        }
        
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    if (p.charAt(j - 2) != '.' && s.charAt(i - 1) != p.charAt(j - 2)) {
                        dp[i][j] = dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j] || dp[i - 1][j - 2];
                    }
                }
            }
        }
        return dp[m][n];
    }
}