题解 | 通配符匹配

解法一：贪心

• 如果i和j标记的字符正好相等或者j字符是'?'匹配成功，则"移除"i和j元素，即自增i、j。
  否则如果j字符是✳(*号)依然可以匹配成功，则用istart和jstart分别标记i元素和j元素之后自增j。
• 否则如果istart>-1说明之前匹配过✳，因为✳可以匹配多个字符，所以这里要再次利用这个最近匹配过的✳匹配更多的字符，移动i标记istart的下一个字符，再让istart重新标记i元素同时移动j标记jstart的下一个字符。
• 上述三种情况都不满足，则匹配失败，返回false。
  最后当s中的字符都判断完毕，则认为s为空，此时需要p为空或者p中只剩下星号的时候，才能成功匹配。

Java参考代码：

public class Solution {
    public boolean isMatch(String s, String p) {
          if (p==null||p.isEmpty())return s==null||s.isEmpty();
    int i=0,j=0,istart=-1,jstart=-1,slen=s.length(),plen=p.length();
    //判断s的所有字符是否匹配
    while (i<slen){
        //三种匹配成功情况以及匹配失败返回false
        if (j<plen&&(s.charAt(i)==p.charAt(j)||p.charAt(j)=='?')){
            i++;
            j++;
        }else if (j<plen&&p.charAt(j)=='*'){
            istart=i;
            jstart=j++;
        }else if (istart>-1){
            i=++istart;
            j=jstart+1;
        }else {
            return false;
        }
    }
    //s中的字符都判断完毕，则认为s为空，此时需要p为空或者p中只剩下星号的时候，才能成功匹配。
    while (j<plen&&p.charAt(j)=='*')j++;
    return j==plen;
    }
}

复杂度分析：

时间复杂度：
空间复杂度：

解法二：动态规划

• 
• dp[i][j]意思是s的前i个