Problem
Given two strings haystack and needle, return the index of the first occurrence of needle in haystack, or -1 if not found.
Example
Input: haystack = "hello", needle = "ll"
Output: 2Solution
Sliding window comparison. Try every starting position in haystack.
def str_str(haystack, needle):
if not needle:
return 0
n, m = len(haystack), len(needle)
for i in range(n - m + 1):
if haystack[i:i+m] == needle:
return i
return -1function strStr(haystack, needle) {
if (needle === '') return 0;
for (let i = 0; i <= haystack.length - needle.length; i++) {
if (haystack.substring(i, i + needle.length) === needle) return i;
}
return -1;
}int strStr(string haystack, string needle) {
if (needle.empty()) return 0;
int n = haystack.size(), m = needle.size();
for (int i = 0; i <= n - m; i++) {
if (haystack.substr(i, m) == needle) return i;
}
return -1;
}public int strStr(String haystack, String needle) {
if (needle.isEmpty()) return 0;
int n = haystack.length(), m = needle.length();
for (int i = 0; i <= n - m; i++) {
if (haystack.substring(i, i + m).equals(needle)) return i;
}
return -1;
}Complexity
- Time: O((n-m+1) * m)
- Space: O(1)
Explanation
Brute force is fine for small inputs. For huge strings, use KMP algorithm for O(n+m) time.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?