Saturday, November 29, 2014

[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,那么一定有其他好的方法。



3 comments:

  1. 前辈你好,我目前也开始边刷题边用博客记录,想请教你是如何在blogspot上使用markdown编排文档的?搜了很久也没发现合适的方法。感谢🙏

    ReplyDelete
  2. 没弄明白为什么:匹配多个字符:dp[i][j] = dp[i-1][j]

    ReplyDelete
    Replies
    1. James 大哥:
      其实可以写成大致
      else if(p[j-1]=='*')
      dp[i][j] = dp[i][j-1] || dp[i-1][j] ;
      其中 dp[i][j-1] 是处理 * 号当成空串用;
      dp[i-1][j] 是处理 * 当成非空串用,这里的递归思路是 text 的最大前缀串已经匹配 pattern 目前的带有 * 的完整串,也就是说 text 的当前比较的最后那个字符只是个“无关紧要的摆设而已;因为 * 可以是任意内容,任意长度。

      Delete