[leetcode]Wildcard Matching

分析：

* 可以匹配任意個字符，包括0個多個連續的*的作用相當於1個*。* 後無其他字符，則直接匹配出現*p為 *，而*s為字符時，我們有兩種選擇，一種是跳過*p指示的*，也就是令*匹配0個字符，繼續向後匹配。
一種是我們需要用* 匹配多個字符，才能完成匹配。

* 後有其他字符，則在s串中向後找與該非*字符匹配的字符，若沒找到，則不匹配，若找到了，則會有不同的情況。 用s中首次遇到的與p中*後的非*字符匹配 這當然是好的，再看另一種情況。 2.不能用S 中首次遇到的與p中*後的非*字符與之匹配。 如圖所示，用s首次的e與p中的e匹配後，繼續匹配的過程中發生了不匹配，但其實s串和p是匹配的，這就是說，要繼續擴大 * 的作用域，將e也與* 進行匹配。 但是通過前面的情況，我們發現p和s都跑了，p指向了g，s指向了第二個e。所以要記錄下*後面的非*字符的位置，以便在後續發生不匹配時，重新進行匹配。

實現:

 bool isMatch(const char *s, const char *p) {  
    const char *backtrack_s = NULL;
	const char *backtrack_p = NULL;  

	while (*s) {  
		//match 
		if (*p == '?' || *s == *p) {  
			++s;  
			++p;  
		}  
		//don't match.
		else {  
			//meet *
			if (*p == '*') { 
				//skip multiply  *.
				while (*p == '*')  
					++p;  
				if (*p == '\0')   
					return true;  
				//record the next position of *.
				backtrack_s = s;  
				backtrack_p = p;  
			}
			// 
			else {//注意：判斷前面是否出現了*  
				if (backtrack_p) {  
					//注意：在當前位置往後判斷出現不相等的時候，再重新回到下一個位置重新往後比較  
					//其意義是繼續擴大*的作用范圍。
					s = ++backtrack_s;  
					
					p = backtrack_p;//恢復p的位置  
				}  
				//既不匹配，前面又沒有*，這就是真的不匹配了。  
				else return false;  
			}  
		} 
	}  //end while

	while (*p == '*')//處理p末端的*  
		++p;  
	return (*s == '\0' && *p == '\0');  
}