leetcode-字符串-28-实现strStr()

28. 实现 strStr()

描述

• 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
• 对于本题而言，当 needle 是空字符串时我们应当返回 0

示例 1

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

示例 2

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

思路 1

• 使用js提供的indexOf

解法 1

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

思路 2

• 遍历截取字符串对比,从匹配字符串 haystack 中截取出与需查找字符串 needle 长度相等的内容后，对比截取的内容与匹配字符串是否相等，如果相等返回开始截取的下标。
  • 1.needle 的长度为0，直接返回0
  • 2.needle 的字符串长度大于 haystack，肯定不匹配
  • 3.needle 的字符串长度等于 haystack，判断是否相等，相等则匹配否则不匹配
  • 4.剩下的就是 needle 字符串长度小于 haystack 的情况，遍历 haystack.在遍历中判断 将要截取的字符串的首位与 needle 字符串的首位是否相同 ，如果不相同也就不需要后续截取、比较，跳过该次循环

代码 2

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

    // needle字符串为空的情况，返回0
   if(!needle){
       return 0;
       // needle字符串长度大于haystack字符串长度，肯定不匹配
   }else if(needleLen>haystackLen){
       return -1;
       // needle字符串长度等于haystack字符串长度，则直接比较两个字符是否一样即可
   }else if(needleLen === haystackLen){
       return haystack === needle ? 0 : -1;
   }else{
       // needle字符串长度小于haystack字符串长度，遍历开始；
       for(let i =0;i<haystackLen-needleLen;i++){
           // 如果haystack字符的每一项 都不等于 needle的第一项，则肯定不匹配
           if(haystack[i] !== needle[0]){
               continue;
           }
            // 从haystack截取和needle长度一样的字符，和needle比较是否一样
           if(haystack.substring(i,i+needleLen) === needle){
               return i;
           }
       }
   }
   return -1;
};

复杂度分析 2

• 时间复杂度：O(n)

  • 遍历长度可能从 1 到 n -1n−1，假设不同长度出现的概率均等，那么时间复杂度为 (n-1 + 1) / 2(n−1+1)/2时间复杂度即为O(n)

• 空间复杂度：O(1)

  • 使用 2 个额外存储空间。

思路 3

• 双层循环对比字符;从匹配字符串 haystack 的不同位置开始遍历，判断其中是否含有查找字符串 needle。

    如：haystack 为 hello， needle 为 ll，依次判断 he、el、ll、lo是否完全和 ll 相等，相等即返回对应字符串在 haystack 中的下标。

• 1.边界情况处理
• 2.设置最外层循环，遍历次数为 0 - haystack长度减去 needle 的长度。剩余字符串长度小于 needle 长度时，肯定不匹配
• 3.判断匹配字符串 haystack 中该次循环使用到的字符串首尾字母是否与查找字符串 needle 首尾字母相同。
  • 不相等，直接跳过继续遍历。
  • 相等，执行第4步。
• 4.判断查找字符串 needle 的长度
  • 长度为 1，表明匹配成功，直接返回当前长字符串下标即可
  • 长度大于 1，执行第5步
• 5.遍历对比字符串，循环判断匹配字符串 haystack 不同位置的字符是否与匹配字符串 needle 对应位置的字符相等
  • 不相等时，跳出循环，进行下次循环。
  • 到最后一位还未跳出循环表明完全匹配，返回当前遍历次数（即查找字符串在匹配字符串中首次出现的位置)

代码 3

const strStr = function (haystack, needle) {
  const hayLen = haystack.length;
  const nedLen = needle.length;

  if (!needle) {
    return 0;
  } if (nedLen > hayLen) {
    return -1;
  } else if (nedLen === hayLen) {
    return haystack === needle ? 0 : -1;
  } else {
    for (let hasIndex = 0; hasIndex <= hayLen - nedLen; hasIndex++) {
      if (
        haystack[hasIndex] === needle[0] &&
          haystack[hasIndex + nedLen - 1] === needle[nedLen - 1]
      ) {
        if (nedLen === 1) {
          return hasIndex;
        }
        for (let nedIndex = 1; nedIndex < nedLen; nedIndex++) {
          if (haystack[hasIndex + nedIndex] !== needle[nedIndex]) {
            break;
          }
          if (nedIndex === nedLen - 1) {
            return hasIndex;
          }
        }
      }
    }
  }
  return -1;
};

复杂度分析 3

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)