1. 题⽬链接：44.通配符匹配

2. 题⽬描述：

3. 解法（动态规划）：

算法思路：

1. 状态表⽰：

对于两个字符串之间的dp问题，我们⼀般的思考⽅式如下：

i. 选取第⼀个字符串的[0, i] 区间以及第⼆个字符串的[0, j] 区间当成研究对象，结 合题⽬的要求来定义「状态表⽰」；

ii. 然后根据两个区间上「最后⼀个位置的字符」，来进⾏「分类讨论」，从⽽确定「状态转移 ⽅程」。 我们可以根据上⾯的策略，解决⼤部分关于两个字符串之间的dp 问题。 因此，我们定义状态表⽰为： dp[i][j] 表⽰： p 字符串 [0, j] 区间内的⼦串能否匹配字符串s 的 [0, i] 区间内的 ⼦串。

2. 状态转移⽅程：

⽼规矩，根据最后⼀个位置的元素，结合题⽬要求，分情况讨论：

        i. 当s[i] == p[j] 或p[j] == '?' 的时候，此时两个字符串匹配上了当前的⼀个字 符，只能从dp[i - 1][j - 1] 中看当前字符前⾯的两个⼦串是否匹配。只能继承上个 状态中的匹配结果， dp[i][j] = dp[i][j - 1] ；

        ii. 当p[j] == '*' 的时候，此时匹配策略有两种选择：

                • ⼀种选择是： * 匹配空字符串，此时相当于它匹配了⼀个寂寞，直接继承状态dp[i] [j - 1] ，此时dp[i][j] = dp[i][j - 1] ；

                • 另⼀种选择是： * 向前匹配1 ~ n 个字符，直⾄匹配上整个s1 串。此时相当于 从dp[k][j - 1] (0 中所有匹配情况中，选择性继承可以成功的 情况。此时dp[i][j] = dp[k][j - 1] (0 ； 

        iii. 当p[j] 不是特殊字符，且不与s[i] 相等时，⽆法匹配。 三种情况加起来，就是所有可能的匹配结果。 综上所述，状态转移⽅程为：

                ▪ 当s[i] == p[j] 或p[j] == '?' 时： dp[i][j] = dp[i][j - 1] ；

                ▪ 当p[j] == '*' 时，有多种情况需要讨论： dp[i][j] = dp[k][j - 1] (0 ；

优化：

当我们发现，计算⼀个状态的时候，需要⼀个循环才能搞定的时候，我们要想到去优化。优 化的⽅向就是⽤⼀个或者两个状态来表⽰这⼀堆的状态。通常就是把它写下来，然后⽤数学的⽅式 做⼀下等价替换： 当p[j] == '*' 时，状态转移⽅程为： 

dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 2][j - 1] ......我们发现i 是有规律的减⼩的，因此我们去看看dp[i - 1][j] ： 

dp[i - 1][j] = dp[i - 1][j - 1] || dp[i - 2][j - 1] || dp[i - 3] [j - 1] ...... 我们惊奇的发现， dp[i][j] 的状态转移⽅程⾥⾯除了第⼀项以外，其余的都可以⽤dp[i - 1][j] 替代。

因此，我们优化我们的状态转移⽅程为： dp[i][j] = dp[i - 1][j] || dp[i][j - 1] 。

3. 初始化：

由于dp 数组的值设置为是否匹配，为了不与答案值混淆，我们需要将整个数组初始化为 false 。 由于需要⽤到前⼀⾏和前⼀列的状态，我们初始化第⼀⾏、第⼀列即可。

        ◦ dp[0][0] 表⽰两个空串能否匹配，答案是显然的，初始化为true 。

        ◦ 第⼀⾏表⽰s 是⼀个空串， p 串和空串只有⼀种匹配可能，即p 串表⽰为"***" ，此时 也相当于空串匹配上空串。所以，我们可以遍历p 串，把所有前导为"*" 的p ⼦串和空串 的dp 值设为true 。

        ◦ 第⼀列表⽰p 是⼀个空串，不可能匹配上s 串，跟随数组初始化即可。

4. 填表顺序：

从上往下填每⼀⾏，每⼀⾏从左往右。

5. 返回值：

根据状态表⽰，返回dp[m][n] 的值。

C++算法代码: 

class Solution 
{
public:
    bool isMatch(string s, string p) 
    {
        int m=s.size(),n=p.size();
        //优化
        s=" "+s;
        p=" "+p;
        //建表
        vector<vector<int>>dp(m+1,vector<int>(n+1));
        //初始化
        dp[0][0]=true;
        for(int i=1;i<=n;i++)
        {
            if(p[i]=='*')
            {
                dp[0][i]=true;
            }
            else
            {
                break;
            }
        }
        //填表
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                //普通字符
                if(islower(p[j]))
                {
                    if(s[i]==p[j]&&dp[i-1][j-1])
                    {
                        dp[i][j]=true;
                    }
                }
                else if(p[j]=='?')
                {
                    dp[i][j]=dp[i-1][j-1];
                }
                else if(p[j]=='*')
                {
                    dp[i][j]=(dp[i][j-1]||dp[i-1][j]);
                }
            }
        }
        //返回值
        return dp[m][n];
    }
};

Java算法代码：

class Solution
{
	public boolean isMatch(String ss, String pp)
	{
		// 1. 创建 dp 表 
		// 2. 初始化 
		1
			2
			3
			4
			5
			6 // 3. 填表 
			 // 4. 返回结果 
			int m = ss.length(), n = pp.length();
		ss = " " + ss; pp = " " + pp;
		char[] s = ss.toCharArray();
		char[] p = pp.toCharArray();
		boolean[][] dp = new boolean[m + 1][n + 1];
		dp[0][0] = true;
		for (int j = 1; j <= n; j++)
			if (p[j] == '*') dp[0][j] = true;
			else break;

		for (int i = 1; i <= m; i++)
			for (int j = 1; j <= n; j++)
				if (p[j] == '*')
					dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
				else
					dp[i][j] = (p[j] == '?' || p[j] == s[i]) && dp[i - 1][j -
					1];
		return dp[m][n];
	}
}