[LeetCode Road] Implement strStr() - Solution/C++

28. Implement strStr()

Question:

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Clarification: What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

Example:

Input: haystack = "hello", needle = "ll"
Output: 2

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Input: haystack = "", needle = ""
Output: 0

Constraints:

0 <= haystack.length, needle.length <= 5 * 10^4

haystack and needle consist of only lower-case English characters.

Source code

Version 1

Idea:
My bad method got Time Limit Exceeded. Because I used two loop to check each characters of string, record the index by 2 variables if both of characters are equal.

I racked my brains for good solution without using substr(). Finally, I got up and went to online to find answer. I refered to Huahua's Tech Road. The loop repeats haystack.length() - needle.length() times, it can reduce computing time. Use the length of needle to match haystack, if index of j is equal to needle.length(), return index of i.

Time complexity: O(m*n)
Space complexity: O(1)

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (haystack == needle || !needle.length()) return 0;
        const int h = haystack.length();
        const int n = needle.length();
        for(int i = 0; i <= h - n; i++){
            int j = 0;
            while(j < n && haystack[i+j] == needle[j]) j++;
            if(j == n) return i;
        }
        return -1;
    }
};

Version 2

Idea:

Use KMP algorithm to match two strings that can reduce time complexity.

Time complexity: O(m + n)
// m: match's time; n: generate pi table Space complexity: O(n) // n: the number of elements in pi table

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(!needle.length()) return 0;
        int s1 = haystack.length();
        int s2 = needle.length();
        
        vector<int> pi = kmpProcess(needle);
        
        cout << endl;
        for(int i = 0, len = 0; i < s1; ++i){
            while(len > 0 && haystack[i] != needle[len]){
                len = pi[len - 1];
            }
            
            if(haystack[i] == needle[len]){
                len++;
            }
            
            if(len == s2){
                cout << len << endl;
                return i - len  + 1;
            }
        }
        
        return -1;
        
    }
private:
    vector<int> kmpProcess(string s){
        int n = s.length();
        vector<int> pi(n, 0);
        
        for(int i = 1, len = 0; i < n; ++i){
            
            while(len > 0 && s[len] != s[i]){
                len = pi[len - 1];
            }
            
            if(s[len] == s[i]){
                len++;
            }
            
            pi[i] = len;
        }
        return pi;
        
    }
};