【LeetCode】44. Wildcard Matching (2 solutions)

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

解法一：

这题想法参考了https://oj.leetcode.com/discuss/10133/linear-runtime-and-constant-space-solution，

类似于一种有限状态机的做法。

主要思想如下：

由于*匹配多少个字符是不一定的，于是首先假设*不匹配任何字符。

当后续匹配过程中出错，采用回溯的方法，假设*匹配0个字符、1个字符、2个字符……i个字符，然后继续匹配。

因此s需要有一个spos指针，记录当p中的*匹配i个字符后，s的重新开始位置。

p也需要一个starpos指针指向*的位置，当回溯过后重新开始时，从starpos的下一位开始。

class Solution {

public:

    bool isMatch(const char *s, const char *p) {

        char* starpos = NULL;

        char* spos = NULL;

        while(true)

        {

            if(*s ==  && *p == )

            //match all

                return true;

            else if(*s ==  && *p != )

            {//successive *p must be all '*'

                while(*p != )

                {

                    if(*p != '*')

                        return false;

                    p ++;

                }

                return true;

            }

            else if(*s !=  && *p == )

            {

                if(starpos != NULL)

                {//maybe '*' matches too few chars in s

                    p = starpos + ;

                    s = spos + ;

                    spos ++;    //let '*' matches one more chars in s

                }

                else

                //*s is too long

                    return false;

            }

            else

            {

                if(*p == '?' || *s == *p)

                {

                    s ++;

                    p ++;

                }

                else if(*p == '*')

                {

                    starpos = (char*)p;

                    spos = (char*)s;

                    p ++;

                    //start successive matching from "'*' matches non"

                }

                //currently not match

                else if(starpos != NULL)

                {//maybe '*' matches too few chars in s

                    p = starpos + ;

                    s = spos + ;

                    spos ++;    //let '*' matches one more chars in s

                }

                else

                //not match

                    return false;

            }

        }

    }

};

解法二：

模仿Regular Expression Matching的递归做法，小数据集上能过。

当*数目太多时会超时。

class Solution {

public:

    bool isMatch(const char *s, const char *p) {

        if(*p == )

            return (*s == );

        if(*p == '*')

        {

            //case1: *p matches 0 chars in s

            if(isMatch(s, p+))

                return true;

            //case2: try all possible numbers

            while(*s != )

            {

                s ++;

                if(isMatch(s, p+))

                    return true;

            }

            return false;

        }

        else

        {

            if((*s==*p) || (*p=='?'))

                return isMatch(s+, p+);

            else

                return false;

        }

    }

};

以下是我的测试代码，小数据上全部通过：

int main()

{

    Solution s;

    cout << s.isMatch("aa","a") << endl;

    cout << s.isMatch("aa","aa") << endl;

    cout << s.isMatch("aaa","aa") << endl;

    cout << s.isMatch("aa","*") << endl;

    cout << s.isMatch("aa","a*") << endl;

    cout << s.isMatch("ab","?*") << endl;

    cout << s.isMatch("aab","c*a*b") << endl;

    return ;

}

巴特西

【LeetCode】44. Wildcard Matching (2 solutions)

最新文章

热门文章