思路1:动态规划

在给定的模式 p 中,只会有三种类型的字符出现:

  • 小写字母 a-z,可以匹配对应的一个小写字母;
  • 问号 ?,可以匹配任意一个小写字母;
  • 星号 *∗,可以匹配任意字符串,可以为空,也就是匹配零或任意多个小写字母
    其中「小写字母」和「问号」的匹配是确定的,而「星号」的匹配是不确定的,因此我们需要枚举所有的匹配情况。为了减少重复枚举,我们可以使用动态规划来解决本题
    图片说明
    图片说明
    public class Solution {
      public boolean isMatch(String s, String p) {
          int slen=s.length();
          int plen=p.length();
          boolean[][] dp=new boolean[slen+1][plen+1];
          dp[0][0]=true;
          for(int j=1;j<=plen;j++){
              if(p.charAt(j-1)=='*'){
                  dp[0][j]=true;
              }
              else{
                  break;
              }
          }
          for(int i=1;i<=slen;i++){
              for(int j=1;j<=plen;j++){
                  if(p.charAt(j-1)=='*'){
                      dp[i][j] = dp[i-1][j] || dp[i][j-1];
                  }
                  else if(s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='?'){
                      dp[i][j] = dp[i-1][j-1];
                  }
              }
          }
          return dp[slen][plen];
      }
    }

复杂度分析

  • 时间复杂度:O(mn),其中 m 和 n 分别是字符串 s 和模式 p 的长度。
  • 空间复杂度:O(mn),即为存储所有 (m+1)(n+1)个状态需要的空间。此外,在状态转移方程中,由于 dp[i][j] 只会从 dp[i][..] 以及 dp[i−1][..] 转移而来,因此我们可以使用滚动数组对空间进行优化,即用两个长度为 n+1的一维数组代替整个二维数组进行状态转移,空间复杂度为 O(n)。

思路2:贪心

本题难点在于处理星号的匹配,用iStar和jStar表示星号在s和p中匹配的位置,初始值为-1,i和j表示当前匹配的位置,匹配过程如下:

  • 如果s和p中字符匹配,则分别自增i和j
  • 否则如果p中当前字符为星号,则标记iStar和jStar,同时自增j
  • 否则如果iStar >= 0,表示之前匹配过星号,因为星号可以匹配任意字符串,所以继续递增i,同时移动j为jStar下一个字符
  • 否则返回false
  • 当s中字符匹配完,p中字符不能有除星号以外字符
    bool isMatch(string s, string p) {
          int i = 0, j = 0, iStar = -1, jStar = -1, m = s.size(), n = p.size();
          while (i < m) {
              if (j < n && (s[i] == p[j] || p[j] == '?')) {
                  ++i, ++j;//i,j向后瞬移
              } else if (j < n && p[j] == '*') {
              //记录如果之后序列匹配不成功时, i和j需要回溯到的位置
                  iStar = i;//记录星号,*可以匹配空字符
                  jStar = j++;
                  //记录星号 并且j移到下一位 准备下个循环s[i]和p[j]的匹配
              } else if (iStar >= 0) {
                  //发现字符不匹配且没有星号出现 但是istar>0 说明可能是*匹配的字符数量不对 这时回溯
                  i = ++iStar;
                  //i回溯到istar+1 因为上次从s串istar开始对*的尝试匹配已经被证明是不成功的(不然不会落入此分支) 
                  //所以需要从istar+1再开始试 同时inc istar 更新回溯位置
                  j = jStar + 1;
                  //j回溯到jstar+1 重新使用p串*后的部分开始对s串istar
                  //(这个istar在上一行已经inc过了)位置及之后字符的匹配 
              } else return false;
          }
          while (j < n && p[j] == '*') 
               ++j;//去除多余星号
          return j == n;
      }