[Leetcode C++] Implement strStr

Problem

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Analysis

Brute force. Assume haystack has length n, and the needle has length m. We have
Time complexity: O(m*n)

Solution

 

class Solution {
public:
    int strStr(string haystack, string needle) {
        
        if(needle.size() == 0) return 0;
        
        for(int i=0; i<haystack.size(); i++){
            
            if(haystack.size()-i < needle.size()) return -1;
            int j =0;
            for(; j<needle.size(); j++){
                if(haystack[i+j]!=needle[j]){
                    break;
                }
            }
            
            //found
            if(j==needle.size()){
                return i;
            }
        }
        
        return -1;
    }
};

Leave a Reply

Your email address will not be published. Required fields are marked *

*