Algorithm Puzzles everyday every week sometimes: Implement strStr()
Puzzle
Puzzle from leetcode:
Implement strStr().
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Solution
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
33
34
| class Solution {
public:
int strStr(const std::string& haystack, const std::string& needle) {
if (needle.empty()) {
return 0;
}
if (needle.size() > haystack.size()) {
return -1;
}
auto needleIt = needle.begin();
int index = -1;
for (auto haystackIt = haystack.begin(); haystackIt != haystack.end();
++haystackIt) {
if (*needleIt == *haystackIt) {
if (index < 0) {
index = std::distance(haystack.begin(), haystackIt);
}
needleIt++;
if (needleIt == needle.end()) {
return index;
}
} else if (index >= 0) {
haystackIt = haystack.begin() + index;
index = -1;
needleIt = needle.begin();
}
}
return -1;
}
};
|
![]()
