28. 实现 strStr().md

BF

var strStr = function(haystack, needle) {
  if (!needle) return 0;
  let lenN = needle.length, lenH = haystack.length
  for (let i = 0; i <= lenH - lenN; i ++) {
    let j;
    for(j = 0; j < lenN; j ++) {
      if (needle[j] != haystack[i + j]) {
        break;
      }
    }
    if (j == lenN) return i;
  }
  return -1;
};

复杂度分析

时间复杂度 $O(N*M)$

空间复杂度 $O(1)$

模式匹配

var strStr = function(haystack, needle) {
  if (!needle) return 0;
  let i = 0, j = 0;
  while(i < haystack.length && j < needle.length) {
    let curH = haystack[i], curN = needle[j];
    if (curH == curN) {
      i ++;
      j ++;
    } else {
      i = i - j + 1;
      j = 0
    }
  }
  if (j >= needle.length) {
    return i - needle.length
  }
  return -1;
};

复杂度分析

时间复杂度 $O(N*M)$

空间复杂度 $O(1)$

RK

var strStr = function(haystack, needle) {
  if (!needle) return 0;
  let targetSum = calcValue(needle);
  let targetLen = needle.length;
  for (let i = 0; i < haystack.length - targetLen + 1; i ++) {
    let curSum = calcValue(haystack.substr(i, targetLen))
    // console.log(curSum, targetSum)
    if (curSum == targetSum) {
      return i
    }
  }
  return -1;
};

function calcValue(str) {
  let sum = 0, len = str.length;
  for(let i = 0; i < len; i ++) {
    sum += (str[i].charCodeAt() - 97) * Math.pow(26, len - i - 1)
  }
  return sum;
}

复杂度分析

时间复杂度 $O(N*M)$

空间复杂度 $O(1)$