X

leetcode 44. Wildcard Matching 解题思路分析

题目大意:

通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 '?''*' 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串(包括空字符串)。

两个字符串完全匹配才算匹配成功。

说明:

  • s 可能为空,且只包含从 a-z 的小写字母。
  • p 可能为空,且只包含从 a-z 的小写字母,以及字符 ?*

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

示例 3:

输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例 4:

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例 5:

输入: s = "acdcb" p = "a*c?b" 输入: false

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=44

解题思路:

这是一道通配符匹配的题,?代表任意一个小写字母,*则代表了0-多个小写字母。难点在于*适配的位数不定,这样我们就不能将字符串s和匹配字符p按照位数一一对应的去比对了。

这道题解题的关键就在于如何巧妙的运用 ‘*’ ,我们先来看匹配字符串p,如果我们将p中的所有星号都忽略掉,那么p就会变成N段有小写字母和问号组成的多个子字符串。比如:p=”abcd*fg?h**ijk”;去掉星号之后就会剩下[abcd,fg?h,ijk]三个子字符串,由于星号可以匹配0-多位,所以问题就简化为,字符串s中是否顺序包含上述所有的子字符串。

不过还有两点需要注意的地方:

第一,关于p去除星号之后的多个子字符串的首尾两个”abcd”和”ijk”,我们必须保证他们分别必须匹配上字符串s对应的首尾位置。而对于中间的所有子字符串,由于两边都有星号的庇护,所以无需考虑匹配s时对应的位置,只要保证所有的字符串能够在s中顺序被找到即可(区间不能有重叠)。分析至此,我们发现,如果匹配字符串能够是以星号开头并以星号结尾的话,那么我们处理起来就会更加方便,所以我们可以考虑先做剪枝操作,将p和s的首尾非星号字符都先匹配掉。

第二,关于问号的匹配方法。现在问题只剩下了p的某个子字符串是否能够在s中被找到。子字符串可能出现的情况分为以下几种,

  1. 只包含小写字母的情况。这在s中查找比较简单。如果匹配成功,我们可以将s中此字符串以及之前的所有字符全部删掉,以便后续匹配。
  2. 以小写字母开头,中间或末尾包含问号。这和第一种情况比较类似,只不过问号可以匹配任意字符而已。同样匹配后删除s中此字符串以及之前的所有字符。
  3. 以问号开头,后续包含小写字母。我们需要先计算出开头连续出现的问号的个数offset,然后以最先出现的小写字母为起点去s中匹配,此时最先出现的小写字母在s中的位置必须相隔s开头至少offset位数。同样匹配后删除s中此字符串以及之前的所有字符。
  4. 子字符串全部是问号。这种情况也不复杂,只需要按照问号的个数删除s中前几位即可。

思路分析完了,我们总结下流程:

  1. 先剪枝,将p中首尾非星号字符逐一匹配,剩下一个以星号开头并以星号结尾的p。如果p中根本没有星号的话,那么剪枝结束后也就知道结果了。
  2. 用星号分割p,生成多个只含有小写字母及问号的子字符串
  3. 按照顺序匹配s中是否包含上述子字符串

完整代码:

public boolean isMatch(String s, String p) {
    // 匹配掉p开头的所有非星号字符
 while (s.length() > 0 && p.length() > 0) {
  if (p.charAt(0) == '*') {
   break;
  }
        // 匹配成功则将p和s的该位移除
  if (p.charAt(0) == '?' || p.charAt(0) == s.charAt(0)) {
   s = s.substring(1);
   p = p.substring(1);
  } else {
        // 匹配失败,返回false
   return false;
  }
 }
    // 匹配掉p结尾的所有非星号字符
 while (s.length() > 0 && p.length() > 0) {
  if (p.charAt(p.length() - 1) == '*') {
   break;
  }
        // 匹配成功则将p和s的该位移除
  if (p.charAt(p.length() - 1) == '?' || p.charAt(p.length() - 1) == s.charAt(s.length() - 1)) {
   s = s.substring(0, s.length() - 1);
   p = p.substring(0, p.length() - 1);
  } else {
        // 匹配失败,返回false
   return false;
  }
 }
    // 将p用星号分割。注意星号为特殊字符需要转义一下
 String[] pa = p.split("\\*");
    // 分别匹配ps中每个子字符串
 for (String ps : pa) {
        // 子字符串为空则忽略
  if ("".equals(ps)) {
   continue;
  }
        // 如果子字符串长度大于s,则返回false
  if (ps.length() > s.length()) {
   return false;
  }
        // 定义一个变量charOffset,记录子字符串开头的问号个数
  int charOffset = 0;
        // 检查子字符串开头的问号个数
  if (ps.startsWith("?")) {
   for (char c : ps.toCharArray()) {
    if (c == '?') {
     charOffset++;
    } else {
     break;
    }
   }
  }
        // 如果问号个数等于子字符串长度,说明该子字符串全部是问号
        // 则删除s的开头相应的位数。同时将p中的该子字符串替换为空
  if (charOffset == ps.length()) {
   p = p.replaceFirst(Pattern.quote(ps), "");
   s = s.substring(charOffset);
   continue;
  }
        // 如果子字符串中包含小写字母,则查找该子字符串在s中首次出现的位置
  int startIndex = isContainString(s, ps, charOffset);
        // 如果startIndex为-1,说明s中不存在该子字符串,返回false
  if (startIndex == -1) {
   return false;
  }
        // 如果s中存在该子字符串,则将s中此子字符串及其之前的全部字符删去
  p = p.replaceFirst(Pattern.quote(ps), "");
        // 同时将s中此子字符串替换为空,继续循环下一个子字符串
  s = s.substring(startIndex + ps.length());
 }
    // 子字符串全部循环之后如果s已经为空,说明匹配成功。
    // 另外,此时p应该也为空或者只剩下星号字符。
 if ("".equals(s)) {
  return true;
 } else {
        // 如果s还有剩余字符,那么看p是否还有剩余,由于p剩下的只可能是星号
        // 所以,只要p不为空则返回true,否则返回false
  if (!"".equals(p)) {
   return true;
  } else {
   return false;
  }
 }
}
// 查看s中是否包含p的子字符串
private int isContainString(String s, String p, int charOffset) {
 int sLength = s.length();
 int pLength = p.length();
    // 如果子字符串的长度大于s,返回-1
 if (pLength > sLength) {
  return -1;
 }
    // 将子字符串p的开头问号都删掉
 p = p.substring(charOffset);
    // 重新计算p的长度
 pLength = p.length();
    // 循环字符串s
 for (int i = charOffset; i < sLength; i++) {
        // 先找到s中与p的首字符相同的字符的位置
  if (s.charAt(i) == p.charAt(0) && sLength - i >= pLength) {
            // 如果找到,开始循环p
   for (int j = 0; j < pLength; j++) {
                // 如果p的当前字符不是问号或者不等同于s对应位置的字符,
                // 则退出p循环,继续在s中寻找下一个与p的首字符相同的字符的位置
    if (p.charAt(j) != '?' && p.charAt(j) != s.charAt(i + j)) {
     break;
    } else {
                // 如果循环到最后一位都能匹配上,则说明匹配成功,返回对应的位置。
                // 注意循环开始前已将问号去除,所以位置不是i,而是i减去开头问号的长度。
     if (j == pLength - 1) {
      return i - charOffset;
     }
    }
   }

  }
 }
 return -1;
}

本解法用时为36毫秒

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-44-wildcard-matching-解题思路分析/
Categories: leetcode
admin:

View Comments (0)