4ms solution C++ for beginners


  • 0
    V

    Two pointers, i and j, one to traverse haystack, the other to traverse needle. The basic idea is to store the value of the index for when there is first match. As soon as there is a mismatch, want to set the i index back to the value of the index for when there was a first match + 1. And start the process again. Of course this is the naiive way.

    int strStr(string haystack, string needle) {
         
        if (needle.empty()) return 0;
        
        int i,j =0;  
        int startOfMatch = INT_MAX;
        
        while (i < haystack.size()){
            
            if (haystack[i] == needle[j]){
                startOfMatch = min(startOfMatch, i); 
                ++j; ++i;
            }
            else{
                if (startOfMatch == INT_MAX) startOfMatch = 0;
                i = ++startOfMatch; 
                j = 0; 
            }
            if (j==needle.size()) return startOfMatch;
        }
        return -1;
         
        
    }

Log in to reply
 

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