String Matching Pattern matching
578. Find the Index of the First Occurrence in a String
You are given two strings, haystack and needle. Return the index where needle first appears in
haystack, or -1 if it does not appear at all.
needle appears at index i when the letters of haystack from index i on spell out needle, in order
and next to each other. Indexes start at 0. If needle appears more than once, return the smallest index.
Example 1
Input: haystack = "bananarama", needle = "anar"
3Explanation: At index 1 the letters a, n, a match, but the next letter is n, not r. The first full match
starts at index 3.
Example 2
Input: haystack = "cat", needle = "cats"
-1Explanation: needle is longer than haystack, so it cannot appear in it.
Example 3
Input: haystack = "tictactic", needle = "tic"
0Explanation: tic appears at index 0 and at index 6. The first one counts.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ haystack.length, needle.length ≤ 105haystackandneedlehold only lowercase English letters.
Clarifying questions
What you would ask an interviewer before writing any code.