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


  • 1
    Y

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

  • 0
    Y

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


  • 0
    K

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


  • 0
    Q

    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


Log in to reply
 

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