dp[i][j]表示s的前i个是否能被p的前j个匹配。
dp[0][0]初始化为true
状态转移方程:

  1. 如果 p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1];(比如"aa"和"aa")
  2. 如果 p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];(因为"."可以表示任意单个字符,所以不需要比较s了)
  3. 如果 p.charAt(j) == '*':
    1. 如果 p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2] //比如"baab"和"bc*aab" c*只能为空。
    2. 如果 p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
      • dp[i][j] = dp[i-1][j] //比如"aa"和"a*",a*表示一个a
      • dp[i][j] = dp[i][j-1] //比如"aaa"和"a*",a*表示多个a
      • dp[i][j] = dp[i][j-2] //a*表示空
public class Solution {
    public boolean isMatch(String s, String p) {
        if(s==null||p==null) return false;
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;//初始化
        //预处理 "aab"  "c*aab"这种情况
        for (int i = 1; i <= p.length(); i++) {
            if (p.charAt(i - 1) == '*' && dp[0][i - 2]) {
                dp[0][i] = true;
            }
        }
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= p.length(); j++) {
                if (p.charAt(j - 1) == s.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                if (p.charAt(j - 1) == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                if (p.charAt(j - 1) == '*') {
                    if (p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.') {//如果前一个元素不匹配 且不为任意元素
                        dp[i][j] = dp[i][j - 2];
                    } else {
                        dp[i][j] = (dp[i][j - 1] || dp[i - 1][j] || dp[i][j - 2]);
                        /*
                         dp[i][j] = dp[i][j-1] // 单个字符匹配的情况
                         dp[i][j] = dp[i-1][j] // 多个字符匹配的情况
                         dp[i][j] = dp[i][j-2] // 没有匹配的情况
                         */
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}
Last modification:April 11th, 2020 at 10:41 am