LeetCode_44 Wildcard Matching

Link to original problem: 这里写链接内容

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

Related problems:

10 Regular Expression Matching 这里写链接内容

I tried the basic backtracking (recursion) method and the method which has optimization on continuous ‘*’, for this problem and get TLE twice. So I came up with the idea dealing with this problem from the tail of those two string.

public class Solution {
    public boolean isMatch(String s, String p) {
        if(p.length() == ) return (s.length() == );
        if(p.charAt() == '*'){
            if(s.length() == ) return isMatch(s, p.substring());
            else return isMatch(s, p.substring()) || isMatch(s.substring(), p);
        }
        else{
            if(s.length() == ) return false;
            else if(s.charAt() == p.charAt() || p.charAt() == '?') return isMatch(s.substring(), p.substring());
            else return false;
        }
    }
}
           

This code failed on:

“aaabbbaabaaaaababaabaaabbabbbbbbbbaabababbabbbaaaaba”

“a*******b”

public class Solution {
    public boolean isMatch(String s, String p) {
        if(p.length() == ) return (s.length() == );
        if(p.charAt() == '*'){
            if(s.length() == ) return isMatch(s, p.substring());
            else if(p.length() >  && p.charAt() == '*') return isMatch(s, p.substring());
            else return isMatch(s, p.substring()) || isMatch(s.substring(), p);
        }
        else{
            if(s.length() == ) return false;
            else if(s.charAt() == p.charAt() || p.charAt() == '?') return isMatch(s.substring(), p.substring());
            else return false;
        }
    }
}
           

And this code failed on:

“babbbbaabababaabbababaababaabbaabababbaaababbababaaaaaabbabaaaabababbabbababbbaaaababbbabbbbbbbbbbaabbb”

“b**bb**a**bba*b**a*bbb**aba***babbb*aa****aabb*bbb***a”