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

Last updated on January 29th, 2025 at 02:29 am

Here, we see a Find the Index of the First Occurrence in a String LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

String, String Matching, Two Pointers

Level of Question

Medium

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

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

1. Problem Statement

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.

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “String Matching (Brute Force)”. The code essentially performs a brute-force search to find the first occurrence of the needle string in the haystack string.

3. Code Implementation in Different Languages

3.1 Find the Index of the First Occurrence in a String C++

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.size(), n = needle.size();
        for (int i = 0; i <= m - n; i++) {
            int j = 0;
            for (; j < n; j++) {
                if (haystack[i + j] != needle[j]) {
                    break;
                }
            }
            if (j == n) {
                return i;
            }
        }
        return -1;        
    }
};

3.2 Find the Index of the First Occurrence in a String Java

class Solution {
    public int strStr(String haystack, String needle) {
        int l1 = haystack.length(), l2 = needle.length();
        if (l1 < l2) {
            return -1;
        } else if (l2 == 0) {
            return 0;
        }
        int threshold = l1 - l2;
        for (int i = 0; i <= threshold; ++i) {
            if (haystack.substring(i,i+l2).equals(needle)) {
                return i;
            }
        }
        return -1;
    }
}

3.3 Find the Index of the First Occurrence in a String JavaScript

var strStr = function(haystack, needle) {
    if (needle.length == 0) return 0;
    for (let i = 0; i < haystack.length; i++) {
        let k = i, j = 0;
        while (haystack[k] == needle[j] && j < needle.length) {
            k++, j++;
        }
        if (j == needle.length) return i;
    }
    return -1;     
};

3.4 Find the Index of the First Occurrence in a String Python

class Solution(object):
    def strStr(self, haystack, needle):
        for i in range(len(haystack) - len(needle)+1):
            if haystack[i:i+len(needle)] == needle:
                return i
        return -1

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(m * n)O(1)
JavaO(m * n)O(n)
JavaScriptO(m * n)O(1)
PythonO(m * n)O(n)
  • The time complexity is the same across all implementations because they all use a brute-force approach to match substrings.
  • The space complexity varies slightly due to differences in how substrings are handled in each language:
    • C++ and JavaScript do not create new substrings during the comparison, so their space complexity is lower.
    • Java and Python create new substrings during each iteration, leading to higher space complexity.
Scroll to Top