判断两个可能包含通配符“？”和“*”的字符串是否匹配。匹配规则如下：

• ‘?’ 可以匹配任何单个字符。

• ‘*’ 可以匹配任意字符串（包括空字符串）。 两个串完全匹配才算匹配成功。

• 1<=|s|, |p| <= 1000

• s 仅包含小写英文字母

• p 包含小写英文字母，？和 *

在线做题地址

样例 1

输入: "aa" "a" 输出: false 

样例 2

输入: "aa" "aa" 输出: true 

样例 3

输入: "aa" "*" 输出: true 说明: '*' 可以替换任何字符串 

样例 4

输入: "ab" "?*" 输出: true 说明: '?' -> 'a' '*' -> 'b' 

算法：动态规划

dp 方程 dp[i][j]表示 s 中前 i 个字符和 p 的前 j 个字符是否匹配成功，如果匹配成功则为 true，否则为 false

初始条件

• s，p 为空串时 能匹配成功 所以 dp[0][0]=true
• s 为空串，p 只为号时候，号也能替换成空串，所以 dp[0][i]=true (p 串从 1 到 i 均是号)，如果有除号以外的字符就匹配不上了

方程转移 对于 dp[i][j]

• p 的第 j 个字符是号，号可以匹配任意串
  • 所以无论是 s 的前 i 个字符和 p 的前 j-1 个字符匹配成功 将*号替换成空串
  • 还是 s 的前 i-1 个字符和 p 的前 j 个字符匹配成功，号替换的长度不限制， 所以可以将号替换成的内容多加上 s[i] 这两种情况都能推出 s 的前 i 个字符和 p 的前 j 个字符匹配成功 if(p[j-1]==’*’) { dp[i][j] = dp[i-1][j] || dp[i][j-1]; }
• p 的第 j 个字符不是*号
  • 如果 dp[i-1][j-1]为 false， 则 s 的前 i-1 个字符和 p 的前 j-1 个字符已经匹配失败了 这时候 dp[i][j]只能为 false 了
• 如果 dp[i-1][j-1]为 true，s 的前 i-1 个字符和 p 的前 j-1 个字符已经匹配成功了 则要看 s 的第 i 个字符 s[i] 和 p 的第 j 个字符 p[j]是否匹配成功 s[i]和 p[j]匹配成功有两种情况 1 是两个字符相同，2 是 p[j]是？ else { if(dp[i-1][j-1] == true) { if(s[i-1]==p[j-1] || p[j-1]==’?’){ dp[i][j]=true; } } }

注意事项

我们 dp 数组下标为 0 的地方要表示空串的答案，所以 dp[i][j]是 s 串的前 i 个字符和 p 串前 j 个字符，这里的 i 和 j 的记数不是从 0 开始的

复杂度分析

时间复杂度

dp 数组状态是 O(NM)的，转移是 O(1)的 所以总时间复杂度是 O(NM)的 N 是 s 串长度，M 是 p 串长度

空间复杂度

dp 数组空间 O(NM)

代码

public class Solution {     public boolean isMatch(String s, String p) {         int sLen = s.length();         int pLen = p.length();         //为了空出边界条件 dp[0][0] 我们 dp 数组从下标为 1 开始使用         // dp[i][j]表示 s 中前 i 个字符和 p 的前 j 个字符是否匹配成功，如果匹配成功则为 true          //初始化 dp 数组         boolean [][]dp = new boolean[sLen + 5][pLen + 5];         for(int i = 0; i <= sLen; i++) {             for(int j = 0; j <= pLen; j++) {                 dp[i][j] = false;             }         }         dp[0][0] = true;          //s 为空，*也可以替换成空串，则当 s 为空 p 为连续的*号时候也是匹配成功的         for(int i = 1; i <= pLen; i++) {             if(p.charAt(i - 1) == '*') {                 dp[0][i] = dp[0][i - 1];             }         }          for(int i = 1; i <= sLen; i++) {             for(int j = 1; j <= pLen; j++) {                 //p 的第 j 个字符是*号，*号可以匹配任意串                 //所以无论是 s 的前 i 个字符和 p 的前 j-1 个字符匹配成功 将*号替换成空串                 //还是 s 的前 i-1 个字符和 p 的前 j 个字符匹配成功，*号替换的长度不限制，                 //所以可以将*号替换成的内容多加上 s[i]                 // 这两种情况都能推出 s 的前 i 个字符和 p 的前 j 个字符匹配成功                 if(p.charAt(j - 1) == '*') {                     dp[i][j] = dp[i - 1][j] || dp[i][j - 1];                 }                  //p 的第 j 个字符不是*号                 //如果 dp[i-1][j-1]为 false，                 //则 s 的前 i-1 个字符和 p 的前 j-1 个字符已经匹配失败了                 //这时候 dp[i][j]只能为 false 了                 // 如果 dp[i-1][j-1]为 true，s 的前 i-1 个字符和 p 的前 j-1 个字符已经匹配成功了                 //则要看 s 的第 i 个字符 s[i] 和 p 的第 j 个字符 p[j]是否匹配成功                 //s[i]和 p[j]匹配成功有两种情况 1 是两个字符相同，2 是 p[j]是？                 else {                     if(dp[i - 1][j - 1] == true) {                         if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {                             dp[i][j] = true;                         }                     }                 }             }         }         return dp[sLen][pLen];      } } 

大佬有話說 (0)