10. 正则表达式匹配 (opens new window)

1.递归(暴力)

模板串匹配时需要考虑两种情况1️⃣单字符2️⃣多字符匹配。本题难点在于如何处理多字符匹配的情况。

出现多字符匹配时，匹配串的当前字符只要和”*“前的元素相同，那么当前匹配串的指针就可以继续往下指。匹配串每个字符都有可能成为模板串多字符匹配的结尾，因此每个匹配串的指针都要进行搜索。

另外注意模板串中的多字符匹配包括零个元素也就是不匹配的情况。退出匹配包括以下几种条件：

• 匹配串和模板串的当前字符不匹配。
• 匹配串还有剩余长度的字符串没有匹配。
• 模板串还有剩余长度的字符串没有匹配，且不为连续多字符匹配模板。

class Solution {
    boolean res = false;
    public boolean isMatch(String s, String p) {
        int curr = 0, pinx = 0;
        dfs(s, p, curr, pinx);
        return res;
    }
    public void dfs(String s, String p, int curr, int pinx) {
        if (curr == s.length() && pinx == p.length()) {
            res = true;
            return;
        }
        if (pinx == p.length()) {
            return;
        }
        if (curr == s.length()) {
            while (pinx < p.length()) {
                if (pinx < p.length() && p.charAt(pinx) != '*') pinx++;
                if (pinx < p.length() && p.charAt(pinx) == '*') {
                    pinx++;
                    if (pinx == p.length()) {
                        res = true;
                    }
                } else {
                    break;
                }
            }
            return;
        }
        //单字符匹配
        if (pinx == p.length() - 1 || pinx + 1 < p.length() && p.charAt(pinx + 1) != '*') {
            if (p.charAt(pinx) == '.' || p.charAt(pinx) == s.charAt(curr)) {
                dfs(s, p, curr + 1, pinx + 1);
            }
        }
        //多字符匹配
        else {
            //固定字符的多字符匹配
            dfs(s, p, curr, pinx + 2);
            if (p.charAt(pinx) != '.') {
                for (int i = curr; i < s.length() && s.charAt(i) == p.charAt(pinx); i++) {
                    dfs(s, p, i + 1, pinx + 2);
                }
            }
            //任意字符的多字符匹配
            else {
                for (int i = curr; i < s.length(); i++) {
                    dfs(s, p, i + 1, pinx + 2);
                }
            }
        }
    }
}

2.动态规划

定义dp[i][j]表示s的前i个字符是否能与p的前j个字符进行匹配。