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:

 1234 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:

 123 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.

Related Topics: Two Pointers String String Matching

## 解題邏輯與實作

 12345678910111213141516 def strStr(haystack: str, needle: str) -> int: h_len = len(haystack) n_len = len(needle) if h_len < n_len: return -1 if h_len == 0 or n_len ==0: return -1 end_idx = h_len-n_len+1 for i in range(0, end_idx): for j in range(0, n_len): if haystack[i+j] != needle[j]: break; if j == n_len-1: return i return -1 

 12 def strStr(haystack: str, needle: str) -> int: return haystack.rfind(needle) 

 1234567891011121314151617181920212223242526272829 def badCharHeuristic(needle: str): NO_OF_CHARS = 256 n_len = len(needle) badChar = [-1]*NO_OF_CHARS for i in range(n_len): badChar[ord(needle[i])] = i; return badChar def strStr(haystack, needle): h_len = len(haystack) n_len = len(needle) if h_len < n_len: return -1 if h_len == 0 or n_len ==0: return -1 badChar = badCharHeuristic(needle) i = 0 end_idx = h_len-n_len while(i <= end_idx): j = n_len-1 while j>=0 and needle[j] == haystack[i+j]: j -= 1 if j<0: return i else: i += max(1, j-badChar[ord(haystack[i+j])]) return -1 

## 更新紀錄

• 2023-02-15 發布
• 2023-02-03 完稿
• 2023-02-03 起稿