[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 如下

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

想法如下

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

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

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

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

code 如下