28.找出字符串中第一个匹配项的下标

链接：28.找出字符串中第一个匹配项的下标
难度：Easy
标签：双指针、字符串、字符串匹配
简介：给你两个字符串  haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回   -1 。

题解 1 - typescript

• 编辑时间：2021-04-20
• 执行用时：84ms
• 内存消耗：40.2MB
• 编程语言：typescript
• 解法介绍：直接调用 indexOf。

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

题解 2 - typescript

• 编辑时间：2021-10-12
• 执行用时：84ms
• 内存消耗：41.8MB
• 编程语言：typescript
• 解法介绍：kmp。

function getNext(needle: string) {
  const next: number[] = [-1];
  for (let i = 1, j = -1; needle[i]; i++) {
    while (j !== -1 && needle[j + 1] !== needle[i]) j = next[j];
    if (needle[j + 1] === needle[i]) j++;
    next[i] = j;
  }
  return next;
}
function strStr(haystack: string, needle: string): number {
  if (needle.length === 0) return 0;
  const next = getNext(needle);
  for (let i = 0, j = -1; haystack[i]; i++) {
    while (j !== -1 && needle[j + 1] !== haystack[i]) j = next[j];
    if (needle[j + 1] === haystack[i]) j++;
    if (!needle[j + 1]) return i - j;
  }
  return -1;
}

题解 3 - typescript

• 编辑时间：2021-10-12
• 执行用时：1504ms
• 内存消耗：42.3MB
• 编程语言：typescript
• 解法介绍：sunday。

function getMap(needle: string) {
  const map: Record<string, number> = {};
  for (let i = 0; needle[i]; i++) map[needle[i]] = i;
  return (c: string) => map[c] ?? -1;
}
function strStr(haystack: string, needle: string): number {
  if (needle.length === 0) return 0;
  const len = needle.length;
  const map = getMap(needle);
  for (let i = 0; haystack[i]; i += len - map(haystack[i + len])) {
    let j = 0;
    while (needle[j] && haystack[i + j] === needle[j]) j++;
    if (!needle[j]) return i;
  }
  return -1;
}