Implement strStr() LeetCode Solution

Table of Contents

Problem Statement:

Implement strStr() LeetCode Solution – Implement strStr().

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.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Explanation:

Iterate over each char in S (haystack) and slice Fsize (no of chars in needles) and check if it’s equal to F (needles). As per the given instruction we will first check if needle is not empty, if needle is empty then we will return -1. We are checking empty string by taking it’s length, if length is 0 it means it is empty string. The reason for taking length of haystack is to check if needle string is bigger then haystack, it means whole needle will not be found in haystack, as needle have more character then haystack, if it is then we can simply return -1,

We will follow the below steps —

1. Take the length of the needle as needleLength.

Scan the haystack from left to right.
Check if substrings of length needleLength are present in it.

NOTE:

if F.len() is zero then return 0
if F.len() > S.len() then return -1

Code:

C++ Solution:

#define len length

class Solution {
public:
    int strStr(string S, string F) {
        int Fsize = F.len();
        if (Fsize == 0)
            return 0;
        
        if (Fsize > S.len())
            return -1;
        
        for (int i = 0; i < S.len(); i++)
        {
            if (S[i] == F[0] and i + Fsize - 1 < S.len() and S.substr(i, Fsize) == F)
                    return i;
        }
        
        return -1;
    }
};

Java Solution:

class Solution {
    public int strStr(String haystack, String needle) {

        if(haystack.contains(needle))
        {
            return haystack.indexOf(needle);
        }
        return -1;
    }
}

Python Solution:

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.find(needle)