source: https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/
C/C++ Solution to LeetCode problem 28. Find the Index of the First Occurrence in a String.
Problem
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
.
Examples
Example 1:
Input: haystack = “sadbutsad”, needle = “sad”
Output: 0
Explanation: “sad” occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
Example 2:
Input: haystack = “leetcode”, needle = “leeto”
Output: -1
Explanation: “leeto” did not occur in “leetcode”, so we return -1.
Constraints
1 <= haystack.length, needle.length <= 104
haystack
andneedle
consist of only lowercase English characters.
Solution
Having two indexes, h
for the haystack and n
for the needle:
- We move through the haystack,
- If
haystack[h] == needle[n]
, then we move both indexes togheter. - If
n
reads the whole needle string, then we have a match, we return the index where it started. - We reset
n
, and we moveh
to the next position where neddle and haystack started to match. return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int strStr(string haystack, string needle) {
int n=0;
int h=0;
while (h<haystack.size()) {
while (haystack[h] == needle[n] && n<needle.size()) {
n++;
h++;
}
if (n == needle.size())
return h - needle.size();
h -= n;
n = 0;
h++;
}
return -1;
}
};