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

tags: Medium,Two Pointers,String

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

解答

Javascript

function strStr(haystack, needle) {
  for (let i = 0; i < haystack.length; i++) {
    if (haystack[i] === needle[0]) {
      if (needle.length === 1) return i;
      for (let j = 1; j < needle.length; j++) {
        if (haystack[i + j] !== needle[j]) break;
        if (j === needle.length - 1) return i;
      }
    }
  }

  return -1;
}

function strStr(haystack, needle) {
  return haystack.indexOf(needle);
}

Time:

$O(mn)$
暴力比對也會過，好神秘，還以為一定要寫個KMP什麼的…
MarsgoatMar 3, 2023

Reference

https://mp.weixin.qq.com/s/eLtQABruL9-Aut5fXl5x-g
分享一下關於indexOf的底層實作

天宇大神表示 : 88 stupid company

回到題目列表