[LeetCode] 28. Implement strStr()

Posted on | In

Problem

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

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

Example 2:

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

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

Explanation

  1. We need to find out the beinning index of the haystack that matches the needle. So, we loop through the haystack, and compare its character with needle. If the first character of needle matches, we need to compare the second character of needle, and so on. It means we also need to loop through the needle.

  2. To keeping track the beinning index of the haystack, we use variable i. Once the first character of needle matches, we need to check the second character of needle, so how do we access the second character of haystack? We can use i+j where j is the loop index of needle, i is the loop index of haystack. If the character not match, we just start the next character of haystack and restart the j to 0, the index of needle. If match and j is at the end of needle, we can return i.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        if (needle.length() > haystack.length()) return -1;
        
        for (int i = 0; i <= haystack.length()-needle.length(); i++) {
            for (int j = 0; j < needle.length(); j++) {
                if (needle.charAt(j) != haystack.charAt(i+j)) {
                    break;
                }
                if (j == needle.length()-1) {
                    return i;
                }
            }
        }
        return -1;
    }
}