10. 正则表达式匹配

题目链接

动态规划

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

dp[i][j]表示s的0_{i-1个字符和p的0}j-1个字符是否匹配。分情况讨论：

• p[j-1]是字母或'.'，则只需要在dp[i-1][j-1]匹配的情况下，当前字母匹配即可
• p[j-1]是'*'，有两种可能
  • 匹配零个前面元素，则dp[i][j-2]匹配即可
  • 匹配大于零个前面元素，则需要当前字母和前面字母匹配

这当中需要注意i的边界情况，数据能保证*前面有字符，就无需考虑j的情况。

观察上面的思路，发现可以将字母与字母的匹配以及字母和'.'的匹配抽离出来，简化代码：

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

    public boolean equal(String s, String p, int i, int j) {
        if (i < 0) {
            return false;
        }
        if (p.charAt(j) == '.') {
            return true;
        }
        return s.charAt(i) == p.charAt(j);
    }
}

这样省去了判断是'.'还是字母，直接匹配即可，也无需再主函数里判断边界条件。