JS算法题之每日一题-11.实现 strStr()

2020-08-05T21:29:05
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9
微信公众号:醉前端关注可了解更多题目。

题 目

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

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

  • 示例 2:

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

说明:当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

答 案

const strStr = (haystack, needle) => {
    if (needle === "") return 0;
    if (haystack === "") return -1;
    let inc = [];
    for (let i = 0; i < needle.length; i++) {
        for (let j = 0; j <= i; j++) {
            if (needle[j] !== needle[i - j]) {
                inc[i] = j + 1;
                break;
            }
            if (j === i && needle[j] === needle[i - j]) {
                inc[i] = j + 1;
            }
        }
    }
    let i = 0;
    let l = needle.length;
    while (i < haystack.length) {
        for (let j = 0; j < l; j++) {
            if (needle[j] !== haystack[i + j]) {
                i += inc[j];
                break;
            }
            if (j === l - 1 && needle[j] === haystack[i + j]) {
                return i;
            }
        }
    }
    return -1;
};
扫一扫关注公众号添加购物返利助手,领红包
当前页面是本站的「Baidu MIP」版。发表评论请点击:完整版 »
因本文不是用Markdown格式的编辑器书写的,转换的页面可能不符合MIP标准。