28. Find the Index of the First Occurrence in a String

Problem Link

Description

---

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 <= 104
• haystack and needle consist of only lowercase English characters.

Solution

---

Python3

class Solution:
    def strStr(self, s: str, target: str) -> int:
        if len(target) == 0 or s == target: return 0
 
        N, M = len(s), len(target)
 
        for i in range(N):
            for j in range(M):
                if i + j >= N or s[i + j] != target[j]: break
 
                if j == M - 1: return i
 
        return -1

Java

class Solution {
   public int strStr(String haystack, String needle) {
      for (int i = 0; ; i++) {
        for (int j = 0; ; j++) {
          if (j == needle.length()) return i;
          if (i + j == haystack.length()) return -1;
          if (needle.charAt(j) != haystack.charAt(i + j)) break;
        }
      }
    }
}