通配符匹配

题目：力扣

解题思路：

一开始用了递归来做，超时了

递归的思路：

1、当字符串和模式串为空时，直接返回true。

2、当字符串不为空但模式串为空时，返回false

3、当字符串为空时，模式串不为空，需要判断，如果模式串全为*，则返回true,否则返回false。

4、当字符串和模式串均不为空时，也需要判断。

先判断第一个字符是否相等

• 当两个字符相等时，相等
• 当模式串字符为？，无论字符串字符是什么，相等

当第一个字符相等时，返回isMatch(s.substring(1,s_len),p.substring(1,p_len))，只需要匹配剩下的就好。

当first不相等时，且模式串字符为*时，这时需要判断

1. 当模式串只有一个*字符，直接返回true
2. 当字符串为空，模式串长度大于1时，返回isMatch(s,p.substring(1,p_len))
3. 其他的情况，直接返回isMatch(s.substring(1, s_len), p) || isMatch(s, p.substring(1, p_len))，前面的是*包含字符的情况，后面的是*代表空串的情况。

当first不相等时，当模式串的字符不为*，其实只是一个普通字母，则直接返回false。

动态规划的思路：

用dp[i][j]表示字符串前i个字符和字符串前j个字符是否匹配，匹配为true,否则为false

比较第i个和第j个字符

当相等，或者模式字符为？时， dp[i][j] = dp[i-1][j-1]。

当模式串字符为*时，dp[i][j] = dp[i-1][j] || dp[i][j-1]

 

class Solution {
    public boolean isMatch(String s, String p) {
        int s_len = s.length();
        int p_len = p.length();
        if(s_len == 0 && p_len == 0){
            return true;
        }
        if(s_len != 0 && p_len == 0){
            return false;
        }

        boolean first = false;
        if(s_len != 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '?') ){
            first = true;
        }
        if(first == true)
            return isMatch(s.substring(1,s_len),p.substring(1,p_len));
        else if(first == false && p.charAt(0) =='*'){
            if(p_len == 1){
                return true;
            }
            if(s_len == 0){
                return isMatch(s, p.substring(1, p_len));
            }
            //这一步，计算有重复导致超时
            return (isMatch(s.substring(1, s_len), p) || isMatch(s, p.substring(1, p_len)));
        }
        else
            return false;
    }
}

class Solution {
    public boolean isMatch(String s, String p) {
        int s_len = s.length();
        int p_len = p.length();
        boolean[][] dp = new boolean[s_len+1][p_len+1];
        dp[0][0] = true;
        for (int i = 1; i <= p_len; ++i) {
            if (p.charAt(i - 1) == '*') {
                dp[0][i] = true;
            } else {
                break;
            }
        }
        for(int i = 1; i <= s_len; i++){
            for(int j = 1; j <= p_len; j++){
                if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1)=='?'){
                    dp[i][j] = dp[i-1][j-1];
                }
                else if(p.charAt(j-1) == '*'){
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                }
            }
        }
        return dp[s_len][p_len];
    }
}