Home Find the Index of the First Occurrence in a String
Post
Cancel

LeetCode #28: Find the Index of the First Occurrence in a String (C/C++).

easy

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 and needle 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 move h 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;
  }
};
This post is licensed under CC BY 4.0 by the author.

Remove Element

Divide Two Integers