# O(n) time, O(1) space C++ 16 ms solution, no tricks, no recursion[explained]

• the idea is very simple, keep finding the earliest possible match for every part of p that doesn't contain any '*' in s, if they all match then it is pretty much true, otherwise not.

``````class Solution {
public:
bool isMatch(string s, string p){
if (p.size() == 0) return s.size()==0;
int laststar = -1;
int start = 0;
int len = 0;
p.push_back('*');

for (int i = 0; i < p.size(); i++){
if (p[i] == '*'){
len = i-1-laststar;
int index = strStr(s, p.substr(laststar+1, len), start);
if (index == -1) return false; //if there is a part that can't match
// if there is no '*' before the first part in p, and it doesn't match as index == 0 in s
if (laststar == -1 && index != 0) return false;
start = index+len;
//I didn't simplified the code here, I am sure it can be cleaner
if (i != p.size() - 1) laststar = i;
while (i < p.size() - 1 && p[i + 1] == '*') i++;
if (i != p.size()-1) laststar = i;
}
}
p.pop_back();
if (p.back() =='*') return true;
if (start == s.size()) return true;
if (laststar != -1) {
int index = strStr(s, p.substr(p.size()-len), s.size()-len);
if (index == s.size()-len) return true;
}
return false;
}

int strStr(string& haystack, string needle, int index) {
if (needle.size() == 0) return 0;
if (haystack.size()==0) return -1;

int last = haystack.size()-needle.size()+1;
int len = needle.size();
for (int i = index; i < last; i++){
int k = 0;
while (k < needle.size() && (needle[k] == haystack[i+k] || needle[k] == '?')) k++;
if (k == needle.size()) return i;
}
return -1;
}
};``````

• substr() can't be performed in constant time. It's a good algorithm but not O(n) unfortunately. :(

• Good simple solution but O(n^2) since you are calling strstr from within a loop and strstr itself has a loop.

• Actually the strstr here used brute force and it should be in O(n^2) time, which makes the whole algorithm O(n^3) I believe

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