首页 > 代码库 > Leetcode#44 Wildcard Matching

Leetcode#44 Wildcard Matching

2024-11-15 14:49:02   202人阅读

原题地址

 

非常有技巧性的一道题，虽然本质上仍然是搜索+回溯，但关键是如何处理模式串里的多余的*，如果处理的不好就超时了。

基本的搜索+回溯算法是这样的，对于原串s和模式串p，依次遍历其字符：

(a) 如果p[j]="*"，依次将p[j+1..p.length]和s[i..s.length]、s[i+1..s.length]、s[i+2..s.length]...匹配，如果全都失败了，将i和j回溯到上一个"*"号位置

(b) 如果s[i]="?"或s[i]=p[j]，说明当前字符匹配，此时i++,j++

(c) 否则，说明当前字符不匹配，回溯至上一个星号位置

可以看出，如果"*"很多，而且总是失败，那么算法的回溯代价是巨大的

 

优化的地方在于：对于情况(a)，如果当前匹配失败，就说明整个匹配失败了，不需要回溯至上一个星号处。

说白了就是，最多回溯到p串的上一个"*"号处，在往前的"*"不用管了。

例如：

   0 1 2 3 4 5 6 7 8 
s: a b c d a c c c
   | |  \ \ \ \
p: a b * c d * a c c
               |
              失配

上面的例子，s[5]!=p[6]，那么最多只需要回溯到第二个星号位置（p[5]="*"），不需要回溯到第一个星号位置（p[2]="*"）。因为回溯到更早的"*"不会产生新的匹配结果。（这个结论以后有机会证明一下）

 

代码：

 1 bool isMatch(const char *s, const char *p) { 2   const char *star = NULL; 3   const char *backup = NULL; 4          5   while (*s) { 6     if (*p == ‘*‘) { 7       backup = s; 8       star = ++p; 9     }10     else if (*p == ‘?‘ || *p == *s) {11       s++;12       p++;13     }14     else if (star) {15       p = star;16       s = ++backup;17     }18     else19       break;20   }21         22   while (*p == ‘*‘)23     p++;24   return !*s && !*p;25 }

 

Leetcode#44 Wildcard Matching


联系
我们