C++ O(n), with only one for loop using window sliding


  • 1
    J

    class Solution {
    public:
    int strStr(string haystack, string needle) {

        int s1=haystack.size();
        int s2=needle.size();
        if(s2==0) return 0;
        else if(s1==0||s1<s2) return -1;
        string substrings=haystack.substr(0,s2);
        if(substrings==needle) return 0;
        for(int i=1;i<s1-s2+1;i++){
            substrings=substrings.substr(1,s2-1);
            substrings=substrings+haystack[i+s2-1];
            if(substrings==needle) return i;
        }
        return -1;
        
    }
    

    };


Log in to reply
 

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