Implement strStr()

Solution

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.

 

Examples

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.

 

Explanation

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

1. Loop through haystack

The loop runs from index 0 to haystack.length() - needle.length() because we are looking for a substring that has same length as needle, so if we are too close to the end of haystack, there won't be enough characters left to match needle.

 

2. Check if a substring of haystack matches needle

For each index i, the code extracts a substring of haystack starting at index i and having a length of needle.length(). This is done using haystack.substring(i, needle.length() + i). Then, the equals(needle) checks if this substring is the same as needle.

 

3. Return the index

As soon as a match is found, the code return the current index i, which represents the first occurence of needle in haystack. If the loop completes without finding needle, the function returns -1, meaning needle is not present in haystack.

 

class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}

The indexOf() method in Java returns the index of the first occurrence of the specified substring(needle) in the string(haystack). If the substring is not found, indexOf() returns -1.

 

This single line replaces the need to manally loop through the haystack and check for occurrences of needle. Internally, indexOf() performs a similar process, but it's optimized and easier to read.