前端练习54 实现strStr()

发表于 分类于 阅读次数：

Leetcode初级算法练习。

题目

题目来自LeetCode

实现strStr()函数。

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

例1:

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

示例 2:

1
2
输入: haystack = "aaaaa", needle = "bba"
输出: -1

当needle是空字符串时我们应当返回0。这与C语言的strstr()以及Java的indexOf()定义相符。

实现

其实就是实现JavaScript中的indexOf函数，对于空字符串indexOf返回的也是0

所以有些答案直接把indexOf方法摆在那里，就是在让人无语了，你来LeetCode的目的是什么呢？刷成绩吗，还是真心想要提高你的算法和逻辑思维的能力呢？

我一开始想对haystack进行一次遍历，声明一个指针来标识内部的needle的遍历的位置，结果发现没有想象的简单

还是应该老老实实用两次遍历来实现，我一开始额外声明了变量来标识循环是否完成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
  if (needle === '') {
    return 0;
  }
  let end = true;
  for (let i = 0; i < haystack.length; i++) {
    let count = i;
    end  = true;
    for (let j = 0; j < needle.length; j++) {
      if (haystack[count++] !== needle[j]) {
        end = false;
        break;
      }
    }
    if (end) {
      return i;
    }
  }
  return -1;
};

执行用时竟然达到了骇人听闻的4912ms。

看了排名在前的答案，进行了优化，优化后执行用时只有100ms：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var strStr = function (haystack, needle) {
  if (needle === '') {
    return 0;
  }
  for (let i = 0; i <= haystack.length - needle.length; i++) {
    for (let j = 0; j < needle.length; j++) {
      if (haystack[i + j] !== needle[j]) {
        break;
      }
      if (j === needle.length - 1) {
        return i;
      }
    }
  }
  return -1;
};

看一下优化的点：

首先就是额外的两个变量根本没有必要，只需要在内层循环判断循环是否是最后一个字符串了即可，没有必要声明flag，而count的话，直接使用i+j代替就行

其次是外层循环没有必要完全循环，如果剩下的长度已经小于needle的长度，那么就没有必要再循环了，因为已经不能再产生结果了。

所以，还是智商的差距。

努力吧。