[LeetCode] 28. Implement strStr()

Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Thought process:
Iterate through haystack. When I find the first character of needle, iterate through needle. Check if all the rest of the characters match.

Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int strStr(String haystack, String needle) {
        for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
            if (haystack.substring(i, i + needle.length()).equals(needle)) {
                return i;
            }
        }
        return -1;
    }
}

Time complexity:
Say the length of haystack is h and needle is n. The overall time complexity is O((h - n)n).

Comments

Popular posts from this blog

[LeetCode] 631. Design Excel Sum Formula

[LeetCode] 714. Best Time to Buy and Sell Stock with Transaction Fee

[LeetCode] 269. Alien Dictionary