28. Implement strStr()

Tags

1. String
2. Two Pointers

Implement strStr()

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

题意：

实现strStr()方法 返回在haystack中第一次出现needle的序列号，如果needle不是haystack其中的一部分则返回-1.

分析：

题意很简单，翻译过来就是求一个字符串是否是另一字符串的一部分，如果是，返回第一次出现的位置序号，如果不是就返回-1。

思路：

思路很常规，双向循环比对两个字符串中每个字符是否相等，如果相等返回序列号，否则返回-1。

复杂度

时间复杂度O(n²)

Js实现：

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    const hLen = haystack.length;
    const nLen = needle.length;

    if(!nLen) return 0;
    /*
    *    1. 外层循环到hLen - nLen + 1这个位置考虑后面的长度要与needle一致
    *    2. 只要有一个字符不等就跳出
    */
    for(let i = 0; i < hLen - nLen + 1; i++) {
        for(let j = 0; j < nLen; j++) {
            if(haystack[i+j] != needle[j]) {
                break;
            } else if(j == nLen - 1) {
                return i;
            }
        }

    }
    return -1;

};