题解 | 正则表达式匹配

public class Solution {
    public boolean match(String str, String pattern) {
        int m = str.length();
        int n = pattern.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        for (int j = 1; j <= n; j++) {
            if (pattern.charAt(j - 1) == '*') {
        // 如果是 '*'，在 pattern 中，* 永远是和它前面的那一个字符绑定出现的，比如 "a*"，它们俩就像一个打包的组合，占用了模式串里的 2 个位置
                dp[0][j] = dp[0][j - 2];
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char sChar = str.charAt(i - 1);
                char pChar = pattern.charAt(j - 1);

                if (pChar == '.' || pChar == sChar) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else if (pChar == '*') {
                    char prePChar = pattern.charAt(j - 2);
                    if (dp[i][j - 2]) {
                        dp[i][j] = true;
                    }
                    else if (prePChar == '.' || prePChar == sChar) {
                // 注意这里是 dp[i - 1][j]，意思是 str 消耗了一个字符，但 pattern 还可以继续用这个 '*' 匹配下一个
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
}