# Linear runtime and constant space solution

• 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 *
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()){
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();
}``````

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

• Pretty Nice Solution. Thanks for Sharing!

• "*" is call astroid
lol
neat solution

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

• 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.

• 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.

• 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)))){ ```

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

• 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.

• 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.

• agree. it still needs backtracking.

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

• 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;
}
}``````

• 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.

• 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".

• The code returns "true" actually.

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

• 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).

• 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 *