FXTi's blog
0%

implement-strStr()

Posted on Edited on

Implement strStr() – LeetCode 28

Problem

Description

Implement strStr().

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

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.size() == 0 || haystack.size() == 0) return -1;
        int n_point = 0, result = -1;
        for(unsigned i = 0; i != haystack.size(); ++i){
            if(haystack[i] == needle[0]){
                for(unsigned j = 1; j != needle.size();++j){
                    if(needle[j] != haystack[i+j]) break;
                }
            }
        }
    }
};

思路

目前用的是最简单的暴力法，从头到尾进行比对。构思的时候觉得可以少遍历一些元素，事实证明的确可以，这个问题也被算作“字符串匹配”。时间复杂度$O(n \times m)$，n为haystack长度，m为needle长度，空间复杂度$O(1)$。
耗时$6$ ms，排名$74.57\%$

Better

思路

还可以用Rabin–Karp algorithm算法，比较简单，对一个子串生成HashCode，妙在Hash用的是线性算法。使用29这个素数做底，以这个素数的幂为基。那么对于abc，可以算作$Hash = 1 \times 29^{0} + 2 \times 29^{1} + 3 \times 29^{2}$，则下一步bcd算作$Hash = \frac{Hash}{10} + 4 \times 29^{3}$。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$6$ ms，排名$74.57\%$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
     int charToInt(char c) {
        return (int)(c-'a'+1);
    }
    // 时间复杂度 O(m+(n-m)) = O(n)
    int strStr(string haystack, string needle) {
        int m = needle.size();
        int n = haystack.size();
        if (m == 0) return 0;
        if (m > n) return -1;

        const int base = 29;
        long long max_base = 1;
        long long needle_code = 0;
        long long haystack_code = 0;
        for (int j = m - 1; j >= 0; j--) {
            needle_code += charToInt(needle[j])*max_base;
            haystack_code += charToInt(haystack[j])*max_base;
            max_base *= base;
        }
        max_base /= base; // 子串的最大基
        if (haystack_code == needle_code)
            return 0;
        for (int i = m; i < n; i++) {
            haystack_code = (haystack_code - charToInt(haystack[i-m]) * max_base) * base + charToInt(haystack[i]);
            if (haystack_code == needle_code)
                return i - m + 1;
        }
        return -1;
    }
};