剑指offer-19：正则表达式匹配

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

总体思路是从 s[:1] 和 p[:1] 是否能匹配开始判断，每轮添加一个字符并判断是否能匹配，直至添加完整个字符串 s 和 p 。展开来看，假设s[:i] 与 p[:j] 可以匹配，那么下一状态有两种：

添加一个字符s_i+1后是否能匹配？
添加字符p_i+1后是否能匹配？

动态规划解析：

状态定义：设动态规划矩阵 dp ， dp[i][j] 代表字符串 s 的前 i 个字符和 p 的前 j 个字符能否匹配。
转移方程：需要注意，由于 dp[0][0] 代表的是空字符的状态，因此 dp[i][j] 对应的添加字符是 s[i - 1] 和 p[j - 1] 。
- 当 p[j - 1] = '*' 时， dp[i][j] 在当以下任一情况为true时等于 true：
  - dp[i][j - 2]： 即将字符组合 p[j - 2] * 看作出现 0 次时，能否匹配；
  - dp[i - 1][j] 且 s[i - 1] = p[j - 2]: 即让字符 p[j - 2] 多出现 1 次时，能否匹配；
  - dp[i - 1][j] 且 p[j - 2] = '.': 即让字符 '.' 多出现 1 次时，能否匹配；
- 当 p[j - 1] != '*' 时， dp[i][j] 在当以下任一情况为 true 时等于 true：
  - dp[i - 1][j - 1] 且 s[i - 1] = p[j - 1]： 即让字符 p[j - 1] 多出现一次时，能否匹配；
  - dp[i - 1][j - 1] 且 p[j - 1] = '.'： 即将字符 . 看作字符 s[i - 1] 时，能否匹配；
初始化： 需要先初始化 dp 矩阵首行，以避免状态转移时索引越界。
- dp[0][0] = true： 代表两个空字符串能够匹配。
- dp[0][j] = dp[0][j - 2] 且 p[j - 1] = '\*'：首行 s 为空字符串，因此当 p 的偶数位为 * 时才能够匹配（即让 p 的奇数位出现 0 次，保持 p 是空字符串）。因此，循环遍历字符串 p ，步长为 2（即只看偶数位）。
返回值： dp 矩阵右下角字符，代表字符串 s 和 p 能否匹配。

class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        int m = s.length();
        int n = p.length();
        //dp[i][j]：字符串s的前i个字符和字符串p的前j个字符是否匹配
        boolean[][] dp = new boolean[m + 1][n + 1];
        //初始化
        dp[0][0] = true;
        for (int i = 2; i <= n; i += 2) {
            //字符串的第0个字符和字符串p的第偶数个字符之间的关系
            dp[0][i] = dp[0][i - 2] && p.charAt(i - 1) == '*';
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '*') {
                    if (dp[i][j - 2]) {//情况1
                        dp[i][j] = true;
                    } else if (dp[i - 1][j] && s.charAt(i - 1) == p.charAt(j - 2)) {//情况2
                        dp[i][j] = true;
                    } else if (dp[i - 1][j] && p.charAt(j - 2) == '.') {//情况3
                        dp[i][j] = true;
                    }
                } else {
                    if (dp[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1)) {//情况4
                        dp[i][j] = true;
                    } else if (dp[i - 1][j - 1] && p.charAt(j - 1) == '.') {//情况5
                        dp[i][j] = true;
                    }
                }
            }
        }
        return dp[m][n];
    }
}

刷题篇剑指offer刷题指南

剑指offer-19：正则表达式匹配

相关

标签