通配符匹配

难度：困难

题目描述

给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：

• '?' 可以匹配任何单个字符。
• '*' 可以匹配任意字符序列（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

示例1

输入：s = "aa", p = "a" 输出：false

示例2

输入：s = "aa", p = "*" 输出：true

示例3

输入：s = "cb", p = "?a" 输出：false

题解

判断 $s$ 和 $p$ 是否匹配，需要分别考虑 $s$ 和 $p$ 的每个前缀，用 $m$ 和 $n$ 分别表示 $s$ 和 $p$ 的长度。对于满足 $1\leq j\leq n$ 和 $1\leq i\leq m$ 的每个下标对 $(i,j)$，需要分别计算 $s$ 的前 $i$个字符和 $p$ 的前 $j$ 个字符是否匹配

创建 (m+1)*(n+1) 的二维数组 $dp$，其中 dp[i][j] 为 $s$ 的前 $i$ 个字符和 $p$ 的前 $j$ 个字符是否匹配

当 j=0 时，模式为空，只有空字符串可以匹配，因此动态规划的结果：当 i=0 时，dp[i][j]=true；当 $i>0$ 时，dp[i][0]=false

当 j>0 时，动态规划的状态转移方程如下：

• 当 i=0 且 j>0 时，如果 p[j-1]='*'且 dp[i][j-1]=true 则 dp[i][j]=true，否则 dp[i][j]=false
• 当 i>0 且 j>0 时，考虑以下情况
  • 如果 $p[j-1]\neq '*'$ ，则当 dp[i-1][j-1]=true 且 s[i-1]，p[j-1] 满足字符匹配时 dp[i][j]=true，否则dp[i][j]=false
  • 如果 p[j-1]='*' ，则当 dp[i][j-1]=true 或 dp[i-1][j]=true 时 dp[i][j]=true，否则 dp[i][j]=false

根据动态规划的状态转移方程，计算 dp[i][j] 的顺序为从小到大遍历每一个 $i$，对于每个 $i$ 从小到大遍历每一个 $j$。计算得到 dp[i][j]

想法代码

public class Solution
{
    public static void Main(string[] args)
    {
        string s = "aa";
        string p = "a";
        Solution solution = new Solution();
        bool res = solution.IsMatch(s,p);
        Console.WriteLine(res);
    }

    public bool IsMatch(string s, string p)
    {
        int m = s.Length, n = p.Length;
        bool[] dp = new bool[n + 1];
        dp[0] = true;
        for (int j = 1; j <= n; j++)
        {
            if (p[j - 1] == '*')
            {
                dp[j] = dp[j - 1];
            }
        }
        for (int i = 1; i <= m; i++)
        {
            bool[] dpNew = new bool[n + 1];
            char c1 = s[i - 1];
            for (int j = 1; j <= n; j++)
            {
                char c2 = p[j - 1];
                if (c2 != '*')
                {
                    dpNew[j] = dp[j - 1] && IsCharacterMatch(c1, c2);
                }
                else
                {
                    dpNew[j] = dpNew[j - 1] || dp[j];
                }
            }
            dp = dpNew;
        }
        return dp[n];
    }

    public bool IsCharacterMatch(char c1, char c2)
    {
        return c1 == c2 || c2 == '?';
    }
}