implement-strStr()

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;
}
};