wild card matching

本文主要是介绍wild card matching，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

(http://www.leetcode.com/onlinejudge 倒数第三题）

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).The matching should cover the entire input string (not partial).The function prototype should be:
bool isMatch(const char *s, const char *p)Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

这个题目的非递归算法，被网易有道面试官，面到过。并且要求写出程序，其实非递归算法要考虑的东西还是很多的，如果没有见过算法，真是很难写出来。笔者在这里给出递归和非递归算法。仅供参考

题目分析：

和正则表达式的匹配有点不同的是，在这里*号是不依赖与以前的符号是，是一个通配符。*是一个多重通配符，而*是一个单一通配符。

递归解法

其实题目很容易写出一个递归的方法：

递归方法首先检查输入两个串是否都是空，如果是空，认为已经匹配完毕，直接返回true。

如果被匹配串是空，模式串如果是 *，那么是true

如果模式串是空，那么结果是false

[cpp]  view plain copy  
 class Solution {  
 public:  
      
     bool isMatch(const char *s, const char *p) {  
       
         if(*s == 0 && *p == 0){ //两个串是否都是空，如果是空，认为已经匹配完毕，直接返回true。  
             return true;  
         }  
         if(*s == 0){ //如果被匹配串是空，模式串如果 全是*，那么就是true  
             while(*p == '*') p++;  
             return !(*p);  
         }  
         if(*p == 0){  
             return false;  
         }  
   
         int i;  
         for( i = 0; s[i] && p[i] ; i++){ //匹配过程  
   
             if(s[i] != p[i]){  
                 if(p[i] == '?'){ //单一通配符  
                     continue;  
                 }  
                 else if(p[i] == '*'){ //多重通配符  
                     s += i;  
                     p += i;  
                     return isMatch(s, p + 1) || isMatch(s + 1, p);//匹配和不匹配，两种情况  
                 }  
                 else{  
                     return false;  
                 }  
             }  
         }  
         return isMatch(s + i, p + i); //匹配剩余的  
     }  
 };  

非递归方法

非递归方法的主要思想是，从匹配串和模式串开头匹配，如果发现当前不能匹配了，则检测之前是否出现过 *，如果有*出现过，则模式串跳过当前不匹配的字符，模式串跳过星号。

例如

abbc a*c***

第一次 startLoop

i = 0; a 和 a 匹配成功

i = 1; b 和 * 发现不能匹配，程序流到 case '*', 因为 * 和 b 可以匹配，所以将 p 和 s 各自 + i ，标记 star为真, 重新开始匹配。

第二次 startLoop

i = 0; b 和 c 不能匹配跳到 starcheck 看看之前是不是有 *，如果存在 *，则 s + 1， p 不增加（此时p还是上一个 * 的下一个位置），然后继续匹配

第三次 startLoop:

i = 0; c = c 可以匹配

这时候 s[i] == 0

跳出循环

{

[cpp]  view plain copy  
 while(p[i] == '*')i++;  
         return !(p[i]);  

}

用来检测当 s 串匹配完了以后 p串是不是全为 * ，如果全是*，则可以匹配，否则匹配失败。

[cpp]  view plain copy  
     bool isMatch(const char *s, const char *p) {  
   
         int i;  
         bool star = false;  
   
 startLoop:  
         {  
             for( i = 0; s[i] ; i++){   
                 switch(p[i])  
                 {   
                 case '?':   
                     break;  
                 case '*': //如果当前 为*， 那么匹配上刚刚不能匹配的那个字符，并且将p移动到 * 结束后的 第一个字符  
                     star = true;  //p 每次指向的位置，要么是最开始，要么是 * 结束的第一个位置  
                     p += i;    
                     s += i;  
                     while(*p == '*'){++p;} //检测p是不是后面全是 *  
                     if(!(*p)) return true;  
   
                     goto startLoop; //重新开始循环, p 指向 * 结束后的 第一个 非*  
                 default:  
                     if(s[i] != p[i]){ //如果 s[i] != p[i]  
                         goto starCheck;  
                     }  
                 }  
             }  
         }  
         while(p[i] == '*')i++;  
         return !(p[i]);  
   
 starCheck:  
         {  
             if(star){ //当 s[i] != p[i], 检测 p 之前是不是 *， 如果是 *，那么我们将s 向后移动一个，其实就是枚举 s 到 s[i],和 p[0] 匹配。  
                 s++;   
                 goto startLoop;  
             }  
             return false;  
         }        
     }  