Wildcard Matching

LeetCode #44

Description:

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)

Example:

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

Idea:

方法一： time O(n2) / dp[i+1][j+1]: p[0-i] match s[0-j] or not? 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] */

方法二：time: O(n) /* 假设我们用两个指针分别指向s和p字符串中要匹配的位置，首先分析下通配符匹配过程中会有哪些情况是成功：

1. s的字符和p的字符相等
2. p中的字符是?，这时无论s的字符是什么都可以匹配一个
3. p中遇到了一个*，这时无论s的字符是什么都没关系
4. 之前的都不符合，但是p在之前的位置有一个，我们可以从上一个后面开始匹配
5. s已经匹配完，但是p后面还有很多连续的` 这里1和2的情况比较好处理，关键在于如何处理3和4的情况。当我们遇到一个时，因为之后可能要退回至该位置重新匹配，我们要将它的下标记录下来，比如idxstar。 但是，当我们连续遇到两次4的情况，如何保证我还是能继续匹配s，而不是每次都退回idxstar+1导致循环呢？所以我们还要记录一个idxmatch，用来记录用上一个连续匹配到的s中的下标。 最后，对于情况5，我们用一个循环跳过末尾的跳过就行了。 */

Code:

Method 1 Time: O(n)

class Solution {
public:
    bool isMatch(string s, string p){
        int inds=0, indp=0, indpstar=-1, indsmatch=0;
        int M=s.size();
        int N=p.size();
        while(inds<M){
            if(indp<N && (s[inds]==p[indp] || p[indp]=='?')){
                indp++;
                inds++;
            }
            else if(indp<N && p[indp]=='*'){
                indpstar=indp;
                indp++;
                indsmatch=inds;
            }
            else if(indpstar!=-1){
                inds=indsmatch;
                indsmatch++;
                indp=indpstar+1;
            }
            else{
                return false;
            }

        }

    // 因为1个*能匹配无限序列，如果p末尾有多个*，我们都要跳过
        while(indp<N && p[indp]=='*'){
            indp++;
        }
    // 如果p匹配完了，说明匹配成功
        return indp==p.size();
    }
};

Method 2

#include <iostream>
#include <vector>
#include <climits>
#include <cassert>

using namespace std;

/*
dp[i+1][j+1]: p[0-i] match s[0-j] or not?
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]
*/


bool isMatch(string s, string p) {
    int M=s.size();
    int N=p.size();

    vector<vector<bool>> dp(M+1, vector<bool>(N+1, false));

    dp[0][0]=true;

    for(int i=0; i<=M; ++i){ // i must start from 0, because even if s is empty, p can still match it. But if p is empty, s can only be empty
        for(int j=1; j<=N; ++j){
            if(i>0 && (s[i-1]==p[j-1] || p[j-1]=='?')){
                dp[i][j]=dp[i-1][j-1];
            }
            else if(p[j-1]=='*'){
                if(i==0)
                    dp[i][j]=dp[i][j-1];
                else
                    dp[i][j]=dp[i][j-1]||dp[i-1][j-1]||dp[i-1][j];
            }
        }
    }
    return dp[M][N];        
}


int main(){
    assert(isMatch("aaaaaaaa", "c")==false);
    assert(isMatch("aa", "a?")==true);
    assert(isMatch("aaa", "aa")==false);
    assert(isMatch("aa", "*")==true);
    assert(isMatch("aa", "a*")==true);
    assert(isMatch("aa", "?*")==true);
    assert(isMatch("aa", "c*a*b")==false);
    assert(isMatch("abc", "**d")==false);
}