题目描述

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

题目分析

找字串
返回索引

参数说明

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */

题解即实现

1. 暴力解法

用两个指针,分别指向主串和子串的第一位,依次对比两者是否相等,若相等两者都后移一位,不相等,主串指针回到一开始位置的下一位,子串回到开头第一位,重复上述步骤,直到遍历完主串,

var strStr = function (haystack, needle) {
  let i = (j = 0);
  while (i < haystack.length && j < needle.length) {
    // 相同后移
    if (haystack[i] === needle[j]) {
      i++;
      j++;
    }
    //不相同回退
    else {
      i = i - j + 1;
      j = 0;
    }
  }
  return j === needle.length ? i - j : -1; //判断是溢出还是没找到
};

时间复杂度:O((m-n)n),主串和字串的乘积关系

资源使用情况
- 执行用时：88 ms, 在所有 JavaScript 提交中击败了 56.53%的用户
- 内存消耗：38.3 MB, 在所有 JavaScript 提交中击败了 31.19%的用户
  问题:时间复杂度高

2. KMP 算法

利用已经匹配过的字符信息,构造回退数组,使主串指针不用回退,空间换时间

//填充next数组
function getNext(s) {
  let i = 0;
  let j = -1;
  let next = [];
  next[0] = -1;
  while (i < s.length - 1) {
    if (j == -1 || s[i] === s[j]) {
      next[++i] = ++j;
    } else j = next[j];
  }
  return next;
}
var strStr = function (haystack, needle) {
  let i = (j = 0);
  let next = getNext(needle);
  while (i < haystack.length && j < needle.length) {
    if (j == -1 || haystack[i] === needle[j]) {
      i++;
      j++;
    } else {
      j = next[j];
    }
  }
  return j === needle.length ? i - j : -1;
};

时间复杂度:O(m+n),字串 next 数组构造需要 n,主串不回退遍历 m

资源使用情况
- 执行用时：100 ms, 在所有 JavaScript 提交中击败了 26.08%的用户
- 内存消耗：40.4 MB, 在所有 JavaScript 提交中击败了 5.06%的用户
  问题:内存使用高,回退时存在多余匹配现象

同思路进阶版

var strStr = function (haystack, needle) {
  let i = (j = 0);
  let next = getNext(needle);
  while (i < haystack.length && j < needle.length) {
    if (j == -1 || haystack[i] === needle[j]) {
      i++;
      j++;
    } else {
      j = next[j];
    }
  }
  return j === needle.length ? i - j : -1;
};
function getNext(s) {
  let i = 0;
  let j = -1;
  let next = [];
  next[0] = -1;
  while (i < s.length - 1) {
    if (j == -1 || s[i] === s[j]) {
      i++;
      j++;
      if (s[i] != s[j]) next[i] = j;
      else next[i] = next[j];
    } else j = next[j];
  }
  return next;
}

资源使用情况
- 执行用时：88 ms, 在所有 JavaScript 提交中击败了 56.53%的用户
- 内存消耗：39.7 MB, 在所有 JavaScript 提交中击败了 6.90%的用户

3. BM 算法

通过坏字符散列表和好后缀数组进行不匹配时模式串的移动指引,最大的特点之一是先将模式串和主串对齐,从后往前匹配

var strStr = function (haystack, needle) {
  const m = needle.length;
  const n = haystack.length;
  if (m === 0) {
    return 0;
  }
  const bmBc = generateBmBc(needle);
  const { prefix, suffix } = generateBmGs(needle);
  let i = 0;
  while (i <= n - m) {
    let j;
    for (j = m - 1; j >= 0; --j) {
      if (haystack[i + j] !== needle[j]) break;
    }
    if (j < 0) {
      return i;
    }
    let x = j - bmBc[haystack.charCodeAt(i + j)];
    let y = 0;
    if (j < m - 1) {
      y = moveByBmGs(j, m, suffix, prefix);
    }
    i = i + Math.max(x, y);
  }
  return -1;
};
//生成坏字符散列表,采用数组形式
function generateBmBc(needle) {
  const SIZE = 256;
  const m = needle.length;
  const bmBc = new Array(SIZE).fill(-1);
  for (let i = 0; i < m; ++i) {
    const ascii = needle.charCodeAt(i);
    bmBc[ascii] = i;
  }
  return bmBc;
}
//生成好后缀数组
function generateBmGs(needle) {
  const m = needle.length;
  const suffix = [];
  const prefix = [];
  for (let i = 0; i < m; ++i) {
    suffix[i] = -1;
    prefix[i] = false;
  }
  for (let i = 0; i < m - 1; i++) {
    let j = i;
    let k = 0;
    while (j >= 0 && needle[j] === needle[m - 1 - k]) {
      ++k;
      suffix[k] = j;
      --j;
    }
    if (j === -1) {
      prefix[k] = true;
    }
  }
  console.log(suffix);
  return {
    prefix,
    suffix,
  };
}
function moveByBmGs(j, m, suffix, prefix) {
  let k = m - 1 - j;
  if (suffix[k] !== -1) {
    return j - suffix[k] + 1;
  }
  for (let r = j + 2; r <= m - 1; ++r) {
    if (prefix[m - r]) {
      return r;
    }
  }
  return m;
}

时间复杂度不详

资源使用情况
- 执行用时：104 ms, 在所有 JavaScript 提交中击败了21.96%的用户
- 内存消耗：40.2 MB, 在所有 JavaScript 提交中击败了5.06%的用户

2020-10-15 实现strStr