44. Wildcard Matching

題目

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

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", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
           

• 和之前的 10. Regular Expression Matching 一樣求解

解析

直接用遞歸會逾時，這裡用到了回溯的思想。
 
'?' 比較好處理，++i，++j 即可
 
關鍵是 '*' ，這裡定義了 i 和 j 的回溯點:
每當遇到 '*' 時，
記錄 i 的回溯點 i_recall = i;
記錄 j 的回溯點 j_recall = ++j，這裡選擇 j 自增後的位置，因為此時 j 為 '*'，嘗試用後面的模式來比對該元素。
 
當遇到不能比對的點時，就會進入到第 3 個 if，此時把 i 回溯到 i_recall 後，同時 i_recall 自增，j 回溯到 j_recall，表示将原來記錄的回溯點用 '*' 來比對，再重新做這一輪的比對。
 
最後要把末尾的 '*' 都忽略，若 p[j] 為空則代表比對完成，若還有剩餘元素說明不比對。

// add 44. Wildcard Matching
class Solution_44 {
public:
	bool isMatch(string s, string p) {
		int i = 0, j = 0, j_recall = 0, i_recall = 0;
		while (s[i]) {
			if (p[j] == '?' || s[i] == p[j])
			{
				++i; ++j; continue;
			}
			if (p[j] == '*')
			{
				i_recall = i; j_recall = ++j; continue;
			}
			if (j_recall)
			{
				i = ++i_recall; j = j_recall; continue;
			}
			return
				false;
		}
		while (p[j] == '*')
			++j;
		return !p[j];
	}
};

           

• 牛客網讨論

C/C++基本文法學習

STL

C++ primer