[LeetCode] Wildcard Matching

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

思路1：DP

和Regular Expression Matching很像，这里的'?'相当于Regular Expression中的'.'，但'*'的用法不一样。这里'*'与前一个字符没有联系，并且无法消去前一个字符，但可以表示任意一串字符。递推公式的推导和Regular Expression Matching也基本类似。

p[j-1] == s[i-1] || p[j-1] == '?'：dp[i][j] = dp[i-1][j-1]

p[j-1] == '*'：

1. 匹配0个字符：dp[i][j] = dp[i][j-1]

2. 匹配1个字符：dp[i][j] = dp[i-1][j-1]

3. 匹配多个字符：dp[i][j] = dp[i-1][j]

先用二维数组写，发现会Memory Limit Exceeded

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { public: bool isMatch(const char *s, const char *p) { int m = strlen(s), n = strlen(p); vector<vector<bool>> dp(m+1, vector<bool>(n+1,false)); dp[0][0] = true; for(int i=0; i<m; i++) { for(int j=1; j<n; j++) { if(p[j-1]==s[i-1] || p[j-1]=='?') dp[i][j] = i>0 && dp[i-1][j-1]; else if(p[j-1]=='*') dp[i][j] = dp[i][j-1] || (i>0 && (dp[i-1][j-1] || dp[i-1][j])); } } return dp[m][n]; } };

然后用一维滚动数组改写，发现会Time Limit Exceeded

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: bool isMatch(const char *s, const char *p) { int m = strlen(s), n = strlen(p); vector<bool> dp(m+1, false); for(int i=0; i<m; i++) { bool diag = dp[0]; dp[0] = i==0 ? true : false; for(int j=1; j<n; j++) { int temp = dp[j]; if(p[j-1]==s[i-1] || p[j-1]=='?') dp[j] = i>0 && diag; else if(p[j-1]=='*') dp[j] = dp[j-1] || (i>0 && (diag || dp[j])); diag = temp; } } return dp[n]; } };

思路2：双指针扫描

用DP会TLE，那么一定有其他好的方法。