[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).
Say the length of haystack is h and needle is n. The overall time complexity is O((h - n)n).
Comments
Post a Comment