[LeetCode] 44. Wildcard Matching

轉自LeetCode

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

<Solution>

這題和 Regular Expression Matching 類似

一樣可以用 DP 來解，但要注意幾點

• 在 regular expression 中，*不可以單獨存在，必須要有前綴字元，像是 a*。但是在 wildcard matching，* 是可以單獨存在，例如 s = "abdww", p="*"，這樣是 match 的

所以必須在處理 * 的地方做一些修正

• 遇到  * 的時候，s 前面的字元必須都要是 match 的，或者 pattern 在 * 前得字串，已經可以 match 目前的 string 了 (因為都可以 match 了，再加個 * 不影響)

code 如下

	class Solution {
	public:
	bool isMatch(string s, string p) {
	const int strLen = s.length(), patternLen = p.length();
	//> dynamic programming
	//> dp[i][j] means s[0..i) can be matched by p[0..j)
	vector<vector<bool>> dp(strLen+1, vector<bool>(patternLen+1, false));
	//> initial state
	//> s="", p=""
	dp[0][0] = true;
	//> dp[0][0..strLen] means s = "" and p must end with *
	//> notice: * can on its own, i.e. p = "*"
	for(int j = 1; j <= patternLen; j++) {
	if(p[j-1] == '*') {
	dp[0][j] = dp[0][j-1];
	}
	}
	//> start matching
	for(int i = 1, strIdx = i-1; i <= strLen; i++, strIdx = i-1) {
	for(int j = 1, patternIdx = j-1; j <= patternLen; j++, patternIdx = j-1) {
	if(p[patternIdx] == '*') {
	dp[i][j] = dp[i-1][j] || dp[i][j-1];
	}
	else {
	dp[i][j] = (s[strIdx] == p[patternIdx] || p[patternIdx] == '?') && dp[i-1][j-1];
	}
	}
	}
	return dp[strLen][patternLen];
	}
	};

view raw wildcardMatching_1.cpp hosted with ❤ by GitHub

但這題用 DP 做反而比較慢，有另外一種解法(參考資料)

想法如下

• 當 pattern 字元不是 * 的時候，檢查 s 的字元是否等於 pattern 的字元，或是 pattern 的字元是 ?

• 當 pattern 字元是 *，用 patternStarIdx 記錄 * 的位置，以及用 strStarIdx 記錄相對應的 s 的字元位置

• 當上述條件都不符合，看看 patternStartIdx 是不是有值，代表遇過 *，這時候 patternIdx 一直都在 patternStartIdx  的下一個位置，且 strIdx 跟著 strStarIdx 移動

• 所有情況都不符合，就代表不 match 了

code 如下

	class Solution {
	public:
	bool isMatch(string s, string p) {
	int strIdx = 0, patternIdx = 0, strStarIdx = -1, patternStarIdx = -1;
	while(strIdx < s.length()) {
	if(patternIdx < p.length() && (s[strIdx] == p[patternIdx] || p[patternIdx] == '?')) {
	//> advancing both pointers when (both characters match) or ('?' found in pattern)
	++strIdx;
	++patternIdx;
	}
	else if(patternIdx < p.length() && p[patternIdx] == '*') {
	//> * found in pattern, track index of *
	patternStarIdx = patternIdx++;
	strStarIdx = strIdx;
	}
	else if(patternStarIdx != -1) {
	//> current character didn't match, but last pattern was *
	patternIdx = patternStarIdx + 1;
	strIdx = ++strStarIdx;
	}
	else {
	return false;
	}
	}
	//> check for remaining characters in pattern
	while(patternIdx < p.length() && p[patternIdx] == '*') {
	++patternIdx;
	}
	return (patternIdx == p.length()) ? true : false;
	}
	};

view raw wildcardMatching_2.cpp hosted with ❤ by GitHub