28. 实现 strStr()

题目

实现 strStr()  函数。

给定一个  haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从 0 开始)。如果不存在，则返回   -1。

示例 1:

输入: haystack = "hello", needle = "ll" 输出: 2

题解

双指针

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
  if (needle == "") return 0;
  let i = 0;
  while (i < haystack.length) {
    let ii = i,
      jj = 0;
    while (haystack[ii] == needle[jj]) {
      if (jj - 0 + 1 == needle.length) return i;
      ii++;
      jj++;
    }
    i++;
  }
  return -1;
};

kmp

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
  if (needle == "") return 0;
  let n = haystack.length,
    m = needle.length;
  let next = new Array(m).fill(-1);
  for (let i = 1; i < m; ++i) {
    let j = next[i - 1];
    while (j != -1 && needle[j + 1] != needle[i]) {
      j = next[j];
    }
    if (needle[j + 1] == needle[i]) {
      next[i] = j + 1;
    }
  }
  let match = -1;
  for (let i = 0; i < n; ++i) {
    while (match != -1 && needle[match + 1] != haystack[i]) {
      match = next[match];
    }
    if (haystack[i] == needle[match + 1]) {
      ++match;
      if (match == m - 1) return i - m + 1;
    }
  }
  return -1;
};