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:
Input: haystack = "hello", needle = "ll" Output: 2
Example 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().
Solution 1: Brute Force
Time complexity: O(mn)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua, 4 ms class Solution { public: int strStr(string haystack, string needle) { const int l1 = haystack.length(); const int l2 = needle.length(); for (int i = 0; i <= l1 - l2; ++i) { int j = 0; while (j < l2 && haystack[i + j] == needle[j]) ++j; if (j == l2) return i; } return -1; } }; |
Python3
1 2 3 4 5 6 7 8 |
# Author: Huahua class Solution: def strStr(self, haystack, needle): l1 = len(haystack) l2 = len(needle) for i in range(l1 - l2 + 1): if haystack[i:i+l2] == needle: return i return -1 |