实现 strStr()

题目

难度级别：简单

实现 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() 定义相符。

解题思路

变量i与k，i为当前遍历needle的一个索引，k为若在haystack找到与needle第一个值相等的一个索引。

遍历haysta判断i是否为0。

1.若i为0

判断当前遍历的haystack的项是否小于needle的长度。 若小于，则没有相等值，返回-1；若不小于且haystack的当前项与neelde的第i项值相等，则判断是否neelde的长度为1，若为1，直接返回j的索引，若i的长度不为1，则将j的值赋给k，继续遍历。

2.若i不为0

若haystack的当前项与needle的当前项相等，则i ，若其中索引j与k 1的差刚好等于needle的长度，那么已经匹配到值，直接退出循环；若haystack的当前项与needle的当前项不相等，则需要将j项返回至k的后一项继续遍历。

代码语言：javascript复制

 const strStr = function(haystack, needle) {    
    if (needle.length === 0) return 0
    if (needle.length > haystack.length) return -1

    let i = 0
    let k = -1

    for (let j = 0; j < haystack.length; j  ) {
        if (i === 0) {
            if (haystack.length - j   1 <= needle.length) {
                    return -1
            }
            if (haystack[j] === needle[i]) {
                if(needle.length === 1){
                    return j
                }
                k = j
                i  
            }
        }
        else {
            if (haystack[j] === needle[i]) {
                if ((j - k   1) === needle.length) {
                    break
                }
                i  
            }else{
                j = k
                k  
                i = 0
            }
        } 
    }

    return k === haystack.length ? -1 : k
};

题目来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/implement-strstr

编程算法

0 人点赞