60. Where It Hides
A reader wants to find where a short phrase first hides inside a longer text. You are given the text haystack and the phrase needle, both of lowercase letters. Return the zero-based index of the first position in haystack where needle appears as a contiguous block. If needle does not appear at all, return -1.
A direct approach is fine here: try every starting position in haystack and compare the following characters with needle one by one, stopping at the first mismatch.
Example 1
- Input:
- haystack = "catalogue", needle = "log"
- Output:
- 4
- Explanation:
The phrase log starts at index 3 of catalogue, and nowhere earlier.
Example 2
- Input:
- haystack = "banana", needle = "nab"
- Output:
- -1
- Explanation:
No block of banana equals nab, so the answer is -1.
Constraints
1 ≤ haystack.length, needle.length ≤ 104
Both strings contain only lowercase English letters
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n * m)
- Space
- O(1)