Implement strStr

Posted by chunyang on April 6, 2019

题目

Implement strStr().

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

Example 1:

Input: haystack = “hello”, needle = “ll”

Output: 2

Example 2:

Input: haystack = “aaaaa”, needle = “bba”

Output: -1

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().

解法

  • 使用 KMP 算法时:算法复杂度 O(n+m),空间复杂度 O(m)
  • 时间复杂度:O(n*m)

思路

  • 使用普通的搜索算法去搜索时,就是按部就班去搜索,挨个匹配。这个也是 search 算法。
  • KMP:

代码

class Solution {
private:
    int useSearch(string haystack, string needle) {
        if (needle.empty()) return 0;
        auto pos = search(haystack.begin(), haystack.end(), needle.begin(), needle.end());
        if (pos == haystack.end()) {
            return -1;
        } else {
            return distance(haystack.begin(), pos);
        }
    }
    int useKMP(string haystack, string needle) {
        if (needle.empty()) return 0;
        if (haystack.empty()) return -1;
        int needle_size = needle.size();
        int stack_size = haystack.size();

        int i = 0;
        int j = -1;
        vector<int> next(needle_size, -1);
        next[0] = -1;
        /* build next */
        /*
        cout << "start to build pattern: " << needle_size << ", " << stack_size << endl;
        cout << "stack: " << haystack << " needle: " << needle << endl; */

        while (i < needle_size) {
            while (j > -1 && needle[i] != needle[j]) {
                j = next[j];
            }
            ++i;++j;
            /* cout << "i: " << i << " j: " << j << endl; */
            if (i >= needle_size) break;
            if (needle[i] == needle[j]) {
                next[i] = next[j];
            } else {
                next[i] = j;
            }
        }
        /* cout << "pattern build finish" << endl;
        copy(next.begin(), next.end(), ostream_iterator<int>(cout, ","));
        cout << endl << "next[0] = " << next[0];
        cout << "next[1] = " << next[1] << endl;
        */
        /* search */
        i = 0; j = 0;
        while (i < stack_size) {
            while (j > -1 && haystack[i] != needle[j]) {
                j = next[j];
            }
            ++i;
            ++j;
            if (j == needle_size) {
                return i - j;
            }
        }

        // delete [] next;
        return -1;
    }
public:
    int strStr(string haystack, string needle) {
        return useKMP(haystack, needle);
    }
};

本文完


Creative Commons License
This work is licensed under a CC A-S 4.0 International License.