SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Intuition

The problem requires finding the first occurrence of the substring needle within the string haystack. If needle is not found in haystack, we return -1.

Approach

1. Edge Case Handling:

   Check if needle is empty. If it is, return 0 immediately because an empty needle is always found at the beginning of haystack.

2. Iterate Through haystack:

   Use a loop to iterate through haystack. For each position i in haystack, check if the substring starting at i and of length equal to the length of needle matches needle.

3. Return the Index:

   If a match is found, return the index i where needle starts in haystack.

4. Return -1 if Not Found:

   If the loop completes without finding needle, return -1.

Complexity

Time Complexity:

O((n-m+1) * m) where n is the length of haystack and m is the length of needle. The worst-case scenario involves checking all possible substrings of length m in haystack.

Space Complexity:

O(1) extra space, apart from input space.

Code

C++

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (haystack.length() < needle.length()) {
            return -1;}
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            if (haystack.substr(i, needle.length()) == needle) {
                return i;
            }}
        return -1;
    }};

Python

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

Java

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

JavaScript

var strStr = function (haystack, needle) {
    if (haystack.length < needle.length) {
        return -1;
    }
    for (let i = 0; i <= haystack.length - needle.length; i++) {
        if (haystack.substring(i, i + needle.length) === needle) {
            return i;
        }
    }
    return -1;
};