Find the Index of the First Occurrence in a String - LeetCode Solution in C++, Java, Python

1. Introduction

The problem "Find the Index of the First Occurrence in a String" involves searching for the first appearance of one string (needle) within another (haystack). This is a classic problem in string manipulation, testing understanding of string search algorithms.

2. 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.

3. Solution in C++

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

Explanation:

1. Special case: if needle is empty, return 0.

2. Iterate over haystack with a window size equal to the length of needle.

3. Compare characters of needle with the current window of haystack.

4. If all characters match, return the start index of the window.

5. If needle is not found, return -1.

4. Solution in Java

public int strStr(String haystack, String needle) {
    if (needle.isEmpty()) return 0;
    int n = haystack.length(), m = needle.length();
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        for (; j < m; j++) {
            if (haystack.charAt(i + j) != needle.charAt(j)) break;
        }
        if (j == m) return i;
    }
    return -1;
}

Explanation:

1. Handle the case where needle is an empty string.

2. Loop through haystack, comparing each substring of length m with needle.

3. If every character in the substring matches needle, return the starting index.

4. If the end of haystack is reached without a match, return -1.

5. Solution in Python

def strStr(haystack, needle):
    if not needle:
        return 0
    n, m = len(haystack), len(needle)
    for i in range(n - m + 1):
        if haystack[i:i + m] == needle:
            return i
    return -1

Explanation:

1. Return 0 if needle is empty.

2. Iterate over haystack, taking substrings of length equal to needle.

3. Compare each substring with needle.

4. If a match is found, return the starting index of the substring.

5. Return -1 if no match is found.