10. 正则表达式匹配

动态规划

class Solution {
    int[][] f;
    public boolean isMatch(String s, String p) {
        f = new int[s.length() + 1][p.length() + 1];
        for (int i = 0; i < f.length; i++) {
            for (int j = 0; j < f[i].length; j++) {
                f[i][j] = -1;
            }
        }
        return isMatch(s, p, 0, 0);
    }
    private boolean isMatch(String s, String p, int x, int y) {
        // 使用f[][]二维数组进行记忆优化
        if (f[x][y] != -1) {
            return f[x][y] != 0; 
        }
        int n = s.length() - x, m = p.length() - y;
        if (m == 0) {
            f[x][y] = x;
            return n == 0;
        }
        boolean firstMatch = n > 0 && (s.charAt(x) == p.charAt(y) || p.charAt(y) == '.');
        boolean res;
        if (m >= 2 && p.charAt(y + 1) == '*') {
            // 如果p[j+1]是通配符'*'，则下面的情况只要有一种满足，f[i][j]就是真；
            // f[i][j+2]是真；
            // s[i]可以和p[j]匹配，且f[i+1][j]是真；
            res = isMatch(s, p, x, y + 2) || (firstMatch && isMatch(s, p, x + 1, y));
        } else {
            // 如果p[j+1]不是通配符'*'，则f[i][j]是真，当且仅当s[i]可以和p[j]匹配，且f[i+1][j+1]是真；
            res = firstMatch && isMatch(s, p, x + 1, y + 1);
        }
        f[x][y] = res ? 1 : 0;
        return res;
    }
}

• 时间复杂度 O(mn)，n 表示 s 的长度，m 表示p的长度
• 空间复杂度 O(mn)，n 表示 s 的长度，m 表示p的长度