正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

• ‘.’ 匹配任意单个字符
• ‘*’ 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

题目解析：

我们定义dp[i][j]表示s串前i个字符能否被p串前 j 个字符匹配

• 初始状态

  • dp[0][0] = true ，即两个都是空串，则肯定不匹配

  • 当 i > 0时，dp[i][0]= false，即s串是非空串，p串是空串，则肯定不能够匹配

  • 当 j >0时，dp[0][j] = dp[0][j-2]，即p串不是空的，但是s串是空的，此时想要匹配，必须利用p串中的*来匹配前面的字符0次使得当前p串为空串，才可能匹配

    比如：p串为"a*b*c*d*"

• 目标状态：显而易见最终的答案就是dp[n][m]，n和m分别为s串和p串的长度

• 中间状态转移：从右往左遍历「因为这样可以提前考虑匹配符号.和*」,对于dp[i][j]「最后两个字符下标分别是i-1和j-1」

  • 如果s[i-1] == p[j-1]，则当前两个字符匹配，如果前面的能够匹配，则dp[i][j]能够匹配，即：dp[i][j] = dp[i-1][j-1]
  • 如果s[i-1] != p[j-1]，我们需要先看下p[i-1]是什么，其只有三种可能：普通字符、*,.
    • 如果是普通字符，则直接匹配失败dp[i][j] = false「因为我们是从右往前考虑，前面的通配符影响不到当前字符」
    • 如果当前字符是.，则当前字符可以匹配，则需要看前面的是否能否匹配dp[i][j] = dp[i-1][j-1]
    • 如果当前字符是*，则要看p串其前面的字符「下标为 j-2 」是什么，看看前面的字符能否与s[i-1]匹配
      • 不匹配，即s[i-1] != p[j-2] && p[i-2] != '.'，那么当前*的作用肯定是匹配前面的字符「下标j-2」0次，然后看p[0 ~ j-3]能否和s0 ~ [i-1]匹配，即dp[i][j] = dp[i][j-2]
      • 匹配，即s[i-1] == p[j-2] || p[i-2] == '.'
        • 通过*重复p[j-2] 0次，则最终能否匹配取决于s[0_i-1]和p[0j-3]能否匹配，即dp[i][j] = dp[i][j-2]
        • 通过*重复p[i-2] 1次，则最终能否匹配取决于 s[0 ~ i-2]和p[0 ~ j-3]能否匹配，即dp[i][j] = dp[i-1][j-2]
        • 通过*重复p[i-2] 多次「2次及以上」，则最终能否匹配取决于 s[0~i-2]和p[0 ~j-1]能否匹配「因为是匹配多次，所有我们可以把当前这一次匹配去掉，但是要保留*,因为要进行多次匹配」，即dp[i][j] = dp[i-1][j]

中间状态转移比较复杂，情况分布图如下所示：

java版本：

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

golang版本：

func isMatch(s string, p string) bool {n,m := len(s),len(p)dp := make([][]bool,n+1)for i := 0;i <= n;i++{dp[i] = make([]bool,m+1)}// 初始状态初始化dp[0][0] = truefor j := 2;j <= m;j++{if p[j-1] == '*'{dp[0][j] = dp[0][j-2]}}// 中间状态转移for i := 1;i <= n;i++{for j := 1;j <= m;j++{if s[i-1] == p[j-1] || p[j-1] == '.'{dp[i][j] = dp[i-1][j-1]}else{if p[j-1] >= 'a' && p[j-1] <= 'z'{dp[i][j] = false}else if p[j-1] == '*'{ // 是*if p[j-2] != s[i-1] && p[j-2] != '.'{dp[i][j] = dp[i][j-2]} else{dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j]}}}}   }return dp[n][m]
}