DEV Community

loading...

LeetCode - Implement strStr()

Alkesh Ghorpade
Ruby on Rails and Golang consultant
Originally published at alkeshghorpade.me ・3 min read

Problem statement

Implement strStr().

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

Problem statement taken from: https://leetcode.com/problems/implement-strstr

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: haystack = "", needle = ""
Output: 0
Enter fullscreen mode Exit fullscreen mode

Constraints:

- 0 <= haystack.length, needle.length <= 5 * 10^4
- haystack and needle consist of only lower-case English characters.
Enter fullscreen mode Exit fullscreen mode

Explanation

Iterative implementation (Brute force)

The iteration approach is to use two nested for loops.
Outer loop will iterate over haystack and
for each index we match the haystack string with needle string.
If we reach the end of needle string we return the start index
else we return -1.

A C++ snippet of the above logic is as below.

for (int i = 0; i <= haystack.length() - needle.length(); i++){
    int j;

    for (j = 0; j < needle.length(); j++) {
        if (needle.charAt(j) != haystack.charAt(i + j)) {
            break;
        }
    }

    if (j == needle.length()) {
        return i;
    }
}
Enter fullscreen mode Exit fullscreen mode

The time complexity of the above program is O(m*n).

Recursive implementation

We can solve the problem using recursive approach as below:

int strStr(string haystack, string needle) {
    // ...basic condition check code

    for (int i = 0; i < haystack.length(); i++){
        if (haystack.charAt(i) == needle.charAt(0))
        {
            String s = strStr(haystack.substring(i + 1), needle.substring(1));
            return (s != null) ? haystack.charAt(i) + s : null;
        }
    }

    return null;
}
Enter fullscreen mode Exit fullscreen mode

For very huge strings recursive approach is not suitable.

Using KMP Algorithm

We can use KMP algorithm to solve the problem in O(m + n) time.

Let's check the algorithm below:

- return 0 if needle.size == 0

- return -1 if haystack.size < needle.size

- set i = 0, j = 0
- initialize index

- loop while i < haystack.size
  - if haystack[i] == needle[j]
    - index = i

    - loop while haystack[i] == needle[j] && j < needle.size()
      - i++
      - j++

    - if j == needle.size
      - return index
    - else
      - j = 0
      - i = index + 1
  - else
    - i++

- return -1
Enter fullscreen mode Exit fullscreen mode
C++ solution
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.size() == 0){
            return 0;
        }

        if(haystack.size() < needle.size()){
            return -1;
        }

        int i = 0, j = 0;
        int index;
        while(i < haystack.size()){
            if(haystack[i] == needle[j]){
                index = i;
                while(haystack[i] == needle[j] && j < needle.size()){
                    i++;
                    j++;
                }
                if(j == needle.size()){
                    return index;
                } else {
                    j = 0;
                    i = index + 1;
                }
            } else {
                i++;
            }
        }

        return -1;
    }
};
Enter fullscreen mode Exit fullscreen mode
Golang solution
func strStr(haystack string, needle string) int {
    needleLen := len(needle)
    haystackLen := len(haystack)

    if needleLen == 0 {
        return 0
    }

    if haystackLen < needleLen {
        return -1
    }

    i := 0
    j := 0
    index := 0

    for i < haystackLen {
        if haystack[i] == needle[j] {
            index = i

            for j < needleLen && haystack[i] == needle[j] {
                i++
                j++
            }

            if j == needleLen {
                return index
            } else {
                j = 0
                i = index + 1
            }
        } else {
            i++
        }
    }

    return -1
}
Enter fullscreen mode Exit fullscreen mode
Javascript solution
var strStr = function(haystack, needle) {
    if(needle.length == 0){
        return 0;
    }

    if(haystack.length < needle.length){
        return -1;
    }

    let i = 0, j = 0;
    let index;

    while( i < haystack.length ){
        if( haystack[i] == needle[j] ){
            index = i;
            while( haystack[i] == needle[j] && j < needle.length ){
                i++;
                j++;
            }

            if( j == needle.length ){
                return index;
            } else {
                j = 0;
                i = index + 1;
            }
        } else {
            i++;
        }
    }

    return -1;
};
Enter fullscreen mode Exit fullscreen mode

Let's dry-run our algorithm to see how the solution works.

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

Step 1: needle.size() == 0
        false

Step 2: haystack.size() < needle.size()
        5 < 2
        false

Step 3: i, j, k = 0, 0, 0

Step 4: while i < haystack.size()
        0 < 5
        true

        haystack[i] == needle[j]
        haystack[0] == needle[0]
        'h' == 'l'
        false

        i++
        i = 1

Step 5: while i < haystack.size()
        1 < 5
        true

        haystack[i] == needle[j]
        haystack[1] == needle[0]
        'e' == 'l'
        false

        i++
        i = 2

Step 6: while i < haystack.size()
        2 < 5
        true

        haystack[i] == needle[j]
        haystack[2] == needle[0]
        'l' == 'l'
        true
        index = i
        index = 2

        j < needle.length && haystack[i] == needle[j]
        0 < 2 && haystack[2] == needle[0]
        true && 'l' == 'l'
        true

        i++;
        j++;

        i = 3
        j = 1

        j < needle.length && haystack[i] == needle[j]
        1 < 2 && haystack[3] == needle[1]
        true && 'l' == 'l'
        true

        i++;
        j++;

        i = 4
        j = 2

        j < needle.length && haystack[i] == needle[j]
        2 < 2
        false

Step 7: j == needle.length
        2 == 2
        true

The answer returned is index: 2
Enter fullscreen mode Exit fullscreen mode

Discussion (0)