题目描述：（来自力扣-44）
给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 ‘?’ 和 ‘‘ 匹配规则的通配符匹配：
‘?’ 可以匹配任何单个字符。
‘‘ 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

解题方法1———动态规划

分析：

若没有出现 ‘*’

动态规划需要创建一个数组，用来存放匹配到dp的i j位置，是否相同看前一个位置 i-1 j-1 是否匹配

dp数组初始化

dp(0)(0)=true
遇到前面全是 ‘*’ 的将dp(0)(j)赋值为true;

出现 ‘*’

因为 ‘*’可以匹配0个（||）多个字符
1.匹配0个字符，dp(i)(j)的值与前一个位置dp(i)(j-1)相关
2.匹配多个字符,dp(i)(j)的值与上一个位置dp(i-1)(j)相关

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public boolean isMatch(String s, String p) {
        int sh=s.length();int ph=p.length();
        //定义dp数组  i代表遍历s j代表遍历p
        boolean[][] dp=new boolean[sh+1][ph+1];
        //初始化dp数组
        dp[0][0]=true;
        for(int k=0;k<ph;k++){
            if(p.charAt(k)=='*'){
                dp[0][k+1]=true;
            }else{
                break;
            }
        }
        //开始遍历
        for(int i=1;i<=sh;i++){
            for(int j=1;j<=ph;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];
                }
                //不相等的不用赋值，本身就是false
            }
        }
        //返回
        return dp[sh][ph];
    }

解决方法2———贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public boolean isMatch(String s, String p) {
       int sRight = s.length(), pRight = p.length();
       while (sRight > 0 && pRight > 0 && p.charAt(pRight - 1) != '*') {
           if (s.charAt(sRight-1)==p.charAt(pRight-1)||p.charAt(pRight-1)=='?') {
               --sRight;
               --pRight;
           } else {
               return false;
           }
       }

       if (pRight == 0) {
           return sRight == 0;
       }

       int sIndex = 0, pIndex = 0;
       int sRecord = -1, pRecord = -1;
       
       while (sIndex < sRight && pIndex < pRight) {
           if (p.charAt(pIndex) == '*') {
               ++pIndex;
               sRecord = sIndex;
               pRecord = pIndex;
           } else if (s.charAt(sIndex)==p.charAt(pIndex)||p.charAt(pIndex)=='?') {
               ++sIndex;
               ++pIndex;
           } else if (sRecord != -1 && sRecord + 1 < sRight) {
               ++sRecord;
               sIndex = sRecord;
               pIndex = pRecord;
           } else {
               return false;
           }
       }

       return pIndex>=pRight?true:p.charAt(pIndex)=='*';
   }