Linear runtime and constant space solution


  • 232
    P

    I found this solution from http://yucoding.blogspot.com/2013/02/leetcode-question-123-wildcard-matching.html


    The basic idea is to have one pointer for the string and one pointer for the pattern. This algorithm iterates at most length(string) + length(pattern) times, for each iteration, at least one pointer advance one step.


    Here is Yu's elegant solution in C++

     bool isMatch(const char *s, const char *p) {
            const char* star=NULL;
            const char* ss=s;
            while (*s){
                //advancing both pointers when (both characters match) or ('?' found in pattern)
                //note that *p will not advance beyond its length 
                if ((*p=='?')||(*p==*s)){s++;p++;continue;} 
    
                // * found in pattern, track index of *, only advancing pattern pointer 
                if (*p=='*'){star=p++; ss=s;continue;} 
    
                //current characters didn't match, last pattern pointer was *, current pattern pointer is not *
                //only advancing pattern pointer
                if (star){ p = star+1; s=++ss;continue;} 
    
               //current pattern pointer is not star, last patter pointer was not *
               //characters do not match
                return false;
            }
    
           //check for remaining characters in pattern
            while (*p=='*'){p++;}
    
            return !*p;  
        }
    

    Here is my re-write in Java

    boolean comparison(String str, String pattern) {
            int s = 0, p = 0, match = 0, starIdx = -1;            
            while (s < str.length()){
                // advancing both pointers
                if (p < pattern.length()  && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){
                    s++;
                    p++;
                }
                // * found, only advancing pattern pointer
                else if (p < pattern.length() && pattern.charAt(p) == '*'){
                    starIdx = p;
                    match = s;
                    p++;
                }
               // last pattern pointer was *, advancing string pointer
                else if (starIdx != -1){
                    p = starIdx + 1;
                    match++;
                    s = match;
                }
               //current pattern pointer is not star, last patter pointer was not *
              //characters do not match
                else return false;
            }
            
            //check for remaining characters in pattern
            while (p < pattern.length() && pattern.charAt(p) == '*')
                p++;
            
            return p == pattern.length();
    }

  • 57
    D

    not linear time really, but the code is elegant and can pass large set test cases


  • 3
    R

    Pretty Nice Solution. Thanks for Sharing!


  • -10
    H

    "*" is call astroid
    lol
    neat solution


  • -5
    K

    I think this code has problem, i.e. s="ab" p="*" will return true, however, i think it should return false.


  • 35
    E

    string = "ab*cdec" and pattern = "ab*c" returns false while it should be true (* in pattern is matching *cde in string).

    I think this idea overlook some cases such as we have * in string.

    but yes, i got an accepted in leetcode.


  • 23
    N

    I agree with dtcxzch. The complexity of the algorithm is O(p*s), where p and s are the lengths of the pattern and input strings. An example of such a worst-case input is:

    input: bbbbbbbbbbbb
    pattern: *bbbb

    Thanks for the solution, it's very elegant.


  • 1
    R

    Easy fix for that...change the first if statement to


    if (p < pattern.length() && (pattern.charAt(p) == '?' || (pattern.charAt(p) != '*' && str.charAt(s) == pattern.charAt(p)))){


  • 0
    D

    Alternatively, you could also switch the first 2 if statements (i.e., check for * first).


  • 1
    T

    Hi, kongkonglin,
    For the case you mentioned, it should return true.
    Please look at the 4th example in the original problem description:
    isMatch("aa", "*") → true
    Actually, when p is "*", I think the function should always return true.


  • 0
    A

    I don't see above changes fix the problem. The s is already increased. You need to revert s to old position to do rematch.


  • 2
    B

    agree. it still needs backtracking.


  • 1
    F

    I presume that there is no '*' or '?' in string given, just in pattern.


  • 2
    S

    I got a question regarding your Java Solution.
    For example, s = "ab", p = "a".

    Regarding your code, since the first pair match, s++, p++ which brings s = 1, p = 1.
    In the next loop, the first if condition will give an ArrayIndexOutOfBoundsException since you write

    // advancing both pointers
                if (p < pattern.length()  && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){
                    s++;
                    p++;
                }
    

    pattern.charAt(1) is out of bounds.

    I hold that your C++ code take advantage of "last char in char[] is '/0' " so that it doesn't have this issue.
    Based on your code and my understanding about your idea. I write Java Solution and got Accepted.
    I 'll illustrate my idea below. But one thing I want to point out is that DP doesn't fit this problem so much thanks to leet_nik 's answer in Subhammodi 's DP post because DP require large memory space.

    My understanding is as follows:

    pointer i for s and j for p.
    matchUntil means does not include that char in that particular position.
    Each time I encounter a 'star', I note down its position and the corresponding position in s where this 'star' match until. And then each time I didn't get good match (p[j] != s[i] && p[j] !='?' && p[j] != '*'), I set matchUntil to the next char and j to lastStar+1, i to matchUntil.

    The last character in p need to be check carefully. Otherwise you'll miss a lot a = "ab", p = "'star'b" cases.
    When it doesn't match for last character of p. You cannot stop yet. Since it may be a result of bad matchUntil position. You need to increase the matchUntil position by one.
    Each time you encounter a 'star', you need O(s) to check each separation of s.
    So the overall Run Time is O(sp) for the worst case.

    The code is a little too long. The if(j < p.length()-1) case is mostly the same with its' opposite, so it could be combined.

    public class Solution {
        public boolean isMatch(String s, String p) {
            
            int i = 0,j = 0;
            int matchUntil = 0; // the position in s where last star match until
            int lastStar = -1; // the position in p where last star appear
            while(i < s.length()){
                if(j < p.length()-1){
                    if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '?'){
                        i++;
                        j++;
                    }else if(p.charAt(j) == '*'){ // mark the last star position
                        lastStar = j;
                        matchUntil = i;
                        j = lastStar+1;
                    }else if(lastStar != -1){
                        matchUntil++;
                        i = matchUntil;
                        j = lastStar+1;
                    }else{
                        return false;
                    }
                }else{
                    if(p.length() == 0){return false;}
                    if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '?'){
                        if(i==s.length()-1){return true;} // match exactly
                        else if(lastStar != -1){
                            matchUntil++;
                            i = matchUntil;
                            j = lastStar+1;
                        }else{
                           return false; 
                        }
                    }else if(p.charAt(j) == '*'){
                        return true;
                    }else if(lastStar != -1){
                        matchUntil++;
                        i = matchUntil;
                        j = lastStar+1;
                    }else{
                        return false;
                    }
                }
            }
            
            while(j < p.length())
                if(p.charAt(j++) != '*')
                    return false;
            
            return true;
        }
    }

  • 6
    B

    This is not O(n) ( as pointed out by other people). This is actually DFS back tracking.
    what the pointers do is to save the DFS nodes and back track.


  • 0
    M

    Elegant code! Thacnks.
    However, when s has character '*', it may return wrong answer.
    For example, when s = '*ba', p = '*a'. It will return "false", While the right answer is "true".


  • 0
    G

    The code returns "true" actually.


  • 0
    X

    My slightly faster version by skipping repetitive '*'s http://xiaohuiliucuriosity.blogspot.com/2014/12/wildcard-matching.html.


  • 0
    A

    I feel the time complexity is more like O(s^2 + p^2) because the pointer s and p would move s^2 and p^2 times respectively, but it would be in the same degree as O(s*p).


  • 0
    C

    I can’t figure out why ss++ is needed but s++ will cause time limit exceeded! ?? Can anyone explain a little bit?Thx

        //current characters didn't match, last pattern pointer was *, current pattern pointer is not *
        //only advancing pattern pointer
        if (star!=NULL)
        {
            s=ss+1;
            ss++;
            p=star+1;
            continue;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.