LeetCode #28 - Implement StrStr

Hello fellow devs πŸ‘‹! We have a new LeetCode problem today involving string.

Problem Statement

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().

Constraints:

  • 0 ≀ haystack.length, needle.length ≀ 5 Γ— 104
  • haystack and needle consist of only lower-case English characters.

Examples

Example 1:

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

Example 2:

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

Example 3:

Input: haystack = "", needle = ""
Output: 0

Analysis

This problem can be rephrased in simple words as, given two strings haystack and needle. Find if needle is present in the haystack. We can easily do it by using library methods but since this is an algorithmic problem, we should not do it.

Plus, Implement StrStr is a stupid name for this problem (sorry C lovers πŸ˜›). If I were the mighty owner of the LeetCode, I would name it Find Needle In A Haystack πŸ˜„.

If the needle is present in the haystack, return its starting index, else return -1.

Approach

We will follow the below steps β€”

!. Take the length of the needle as needleLength.

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

Time Complexity

The string is traversed once so the time complexity will be O(n).

Space Complexity

We may have to create n substrings of length 1 each, therefore, the space complexity will also be O(n).

Code

Java

public class ImplementStrStr {

    public int strStr(String haystack, String needle) {
        // Base condition
        if (haystack == null || needle == null) {
            return -1;
        }
        // Special case
        if (haystack.equals(needle)) {
            return 0;
        }
        // length of the needle
        int needleLength = needle.length();
        // Loop through the haystack and slide the window
        for (int i = 0; i < haystack.length() - needleLength + 1; i++) {
            // Check if the substring equals to the needle
            if (haystack.substring(i, i + needleLength).equals(needle)) {
                return i;
            }
        }
        return -1;
    }
}

Python

class ImplementStrStr:
    def strStr(haystack: str, needle: str) -> int:
        # Base conditions
        if haystack is None or needle is None:
            return -1
        # Special case
        if haystack == needle:
            return 0
        # Length of the needle
        needleLength = len(needle)
        # Loop through the haystack and slide the window
        for i in range(len(haystack) - needleLength + 1):
            if haystack[i:i + needleLength] == needle:
                return i
        return -1

JavaScript

var strStr = function (haystack, needle) {
    // Base condition
    if (haystack == null || needle == null) {
        return -1;
    }
    // Special case
    if (haystack === needle) {
        return 0;
    }
    // length of the needle
    const needleLength = needle.length;
    // Loop through the haystack and slide the window
    for (let i = 0; i < haystack.length - needleLength + 1; i++) {
        // Check if the substring equals to the needle
        if (haystack.substring(i, i + needleLength) === needle) {
            return i;
        }
    }
    return -1;
};

Kotlin

class ImplementStrStr {
    fun strStr(haystack: String, needle: String): Int {
        // Special case
        if (haystack == needle) {
            return 0
        }
        // length of the needle
        val needleLength = needle.length
        // Loop through the haystack and slide the window
        for (i in 0 until haystack.length - needleLength + 1) {
            // Check if the substring equals to the needle
            if (haystack.substring(i, i + needleLength) == needle) {
                return i
            }
        }
        return -1
    }
}

Complete Code

Conclusion

Congratulations πŸ‘! We have solved yet another problem from LeetCode involving string.

I hope you enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork πŸ”ͺ and star ⭐ it.

Till next time… Happy coding πŸ˜„ and Namaste πŸ™!


Created and maintained by@Anirudh Sharma
I love to learn and share. Hence, this site has no ads, no affiliation links, or any BS. If you like what you see, give me a thumbs up.

GitHub iconMedium iconTwitter iconFacebook iconLinkedIn iconStackoverflow icon