28. Find the Index of the First Occurrence in a String LeetCode Solution

In this guide we will provide 28. Find the Index of the First Occurrence in a String LeetCode Solution with best time and space complexity. The solution to Find the Index of the First Occurrence in a String problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.

Table of Contents

28. Find the Index of the First Occurrence in a String LeetCode Solution image

Problem Statement of Find the Index of the First Occurrence in a String

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.

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.

Complexity Analysis

  • Time Complexity: O((m – n)n), where m = |\texttt{haystack}| and n = |\texttt{needle}|
  • Space Complexity: O(1)

28. Find the Index of the First Occurrence in a String LeetCode Solution in C++

class Solution {
 public:
  int strStr(string haystack, string needle) {
    const int m = haystack.length();
    const int n = needle.length();

    for (int i = 0; i < m - n + 1; i++)
      if (haystack.substr(i, n) == needle)
        return i;

    return -1;
  }
};
/* code provided by PROGIEZ */

28. Find the Index of the First Occurrence in a String LeetCode Solution in Java

class Solution {
  public int strStr(String haystack, String needle) {
    final int m = haystack.length();
    final int n = needle.length();

    for (int i = 0; i < m - n + 1; ++i)
      if (haystack.substring(i, i + n).equals(needle))
        return i;

    return -1;
  }
}
// code provided by PROGIEZ

28. Find the Index of the First Occurrence in a String LeetCode Solution in Python

class Solution:
  def strStr(self, haystack: str, needle: str) -> int:
    m = len(haystack)
    n = len(needle)

    for i in range(m - n + 1):
      if haystack[i:i + n] == needle:
        return i

    return -1
#code by PROGIEZ

Additional Resources

See also  41. First Missing Positive LeetCode Solution

Feel free to give suggestions! Contact Us