:orphan:

Find the Index of the First Occurrence in a String
==================================================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/

Given two strings ``needle`` and ``haystack``, return the index of the
first occurrence of ``needle`` in ``haystack``, or ``-1`` if ``needle``
is not part of ``haystack``.

 

**Example 1:**

::


   Input: haystack = "sadbutsad", needle = "sad"
   Output: 0
   Explanation: "sad" occurs at index 0 and 6.
   The first occurrence is at index 0, so we return 0.

**Example 2:**

::


   Input: haystack = "leetcode", needle = "leeto"
   Output: -1
   Explanation: "leeto" did not occur in "leetcode", so we return -1.

 

**Constraints:**

- ``1 <= haystack.length, needle.length <= 10``\ :sup:```4```
- ``haystack`` and ``needle`` consist of only lowercase English
  characters.

.. highlight:: python

Pattern
-------
Two Pointers, String, String Matching

Solution
--------
Iterate through each character in ``haystack`` and check if the substring
``haystack[i:i + len(needle)]`` is equal to ``needle``.

Code
----

.. literalinclude:: ../problems/easy/find-the-index-of-the-first-occurrence-in-a-string/find_the_index_of_the_first_occurrence_in_a_string__approach_1.py
    :language: python
    :lines: 10-

Test
----
>>> from find_the_index_of_the_first_occurrence_in_a_string__approach_1 import strStr
>>> strStr('hello', 'll')
2
>>> strStr('aaaaa', 'bba')
-1

Complexity
----------
| :math:`m` is the length of the needle and :math:`n` is the length of the haystack.
| Time: :math:`O(n - m)` — single pass through the haystack
| Auxiliary Space: :math:`O(1)`

.. autofunction:: find_the_index_of_the_first_occurrence_in_a_string__approach_1.strStr