leetcode10-正则表达式匹配

正则表达式匹配

• dp

dp[i][j]表示s[0:i]和p[0:j]是否匹配。

1. 如果i == 0 && j == 0，那么说明两个字符串都没有选择字符，是true
2. 如果j == 0，那么说明匹配串没有字符而原字符串有字符，是false
3. 否则，需要根据字符进行分类讨论（注意：i == 0无法判断是true还是false，需要根据字符值进行判断）
   1. 如果p字符串的字符为，那么需要去比较前一个字符串和当前字符是否相等。如果两个字符相等，那么有两种选择：一种是进行匹配，由于可以匹配无限数量，所以相应的dp值为dp[i-1][j]即匹配串不变而原字符串的位置往前一位，另一种是不去匹配，对应的dp值为dp[i][j-2]。如果两个字符串不相等，那么只能选择不匹配。
   2. 如果p字符串不为*，那么相应的dp值为dp[i-1][j-1] && s.charAt(i-1) == p.charAt(j-1)

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