Leetcode 28 Solution

This article provides solution to leetcode question 28 (implement-strstr).
Categories:
Tags:
Access this page by simply typing in "lcs 28" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/implement-strstr

Thinking Process

The straightforward solution of this question is just to find if the needle exists in each position from the haystack. If needle size is N, and the haystack size is M, the time complexity is O(M * N).

A better solution is to use KMP algorithm, which can achieve linear speed.

Time & Space Complexity

Assuming the length of the haystack is M, the length of the needle is N

  • Time complexity: O(M)
  • Space complexity: O(N)

Solution

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.size();
        int n = needle.size();

        if (n == 0)
            return 0;

        int next[n] = {0};
        int j = 0;
        int i = 1;

        while (i < needle.size())
        {
            while (j > 0 && needle[i] != needle[j])
                j = next[j - 1];
            next[i] = needle[i] == needle[j] ? ++j : 0;
            i++;
        }

        j = 0;
        i = 0;
        while (i < haystack.size() && j < needle.size())
        {
            while (j > 0 && haystack[i] != needle[j])
                j = next[j - 1];
            j = haystack[i] == needle[j] ? ++j : 0;
            i++;
        }

        return j == needle.size() ? i - j : -1;
    }
};