小宋爱睡觉
  • 字符串
Crucials
2022-01-15

字符串

# 字符串

# lc13. 罗马数字转整数简单

题目描述

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
1
2
3
4
5
6
7
8

例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
1
2
3

给定一个罗马数字，将其转换成整数。

示例 1:

输入: s = "III"
输出: 3
1
2

示例 2:

输入: s = "IV"
输出: 4
1
2

示例 3:

输入: s = "IX"
输出: 9
1
2

示例 4:

输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
1
2
3

示例 5:

输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
1
2
3
var romanToInt = function(s) {
  const map = new Map()
  map.set('I', 1)
  map.set('V', 5)
  map.set('X', 10)
  map.set('L', 50)
  map.set('C', 100)
  map.set('D', 500)
  map.set('M', 1000)
  let sum = 0
  for(let i = 0; i < s.length; i++) {
    if(s[i] === 'I' && s[i + 1] && (s[i + 1] === 'V' || s[i + 1] === 'X')) {
      sum += (-1 + map.get(s[i + 1]))
      i++
    } else if(s[i] === 'X' && s[i + 1] && (s[i + 1] === 'L' || s[i + 1] === 'C')) {
      sum += (-10 + map.get(s[i + 1]))
      i++
    } else if(s[i] === 'C' && s[i + 1] && (s[i + 1] === 'D' || s[i + 1] === 'M')) {
      sum += (-100 + map.get(s[i + 1]))
      i++
    } else {
      sum += map.get(s[i])
    }
  }
  return sum
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

时间复杂度O(n)

空间复杂度O(1)

# lc14. 求最长公共前缀简单hot

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例：

输入：strs = ["flower","flow","flight"]
输出："fl"

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
1
2
3
4
5
6

思路：

  1. 要是空数组就返回 ""
  2. 要是数组长度为1， 就返回数组的第一位
  3. 先按长度排序，然后只用对比第一位和最后一位的字符串，比较一下哪一个字符短，循环判断每一位是不是一样， 一样的话继续下一位判断，时间复杂度为On
var longestCommonPrefix = function(strs) {
   strs.sort()
  let short = strs[0]
  let long = strs[strs.length - 1]
  let res = ''
  for(let i = 0; i < short.length; i++) {
    if(short[i] === long[i]) res += short[i]
    else return res
  }
  return res
};
1
2
3
4
5
6
7
8
9
10
11

# lc172. 阶乘后的零中等

题目描述

给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

示例 1：

输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
1
2
3

示例 2：

输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0
1
2
3

示例 3：

输入：n = 0
输出：0
1
2

思路

这道题很简单，有多少个5就有多少个0，我们发现只有5的倍数的阶乘，才会产生5, 所以我们需要看看阶层数有多少个5

var trailingZeroes = function (n) {
  let r = 0;
  while (n > 1) {
    n = Math.floor(n / 5);
    r += n;
  }
  return r;
};
1
2
3
4
5
6
7
8

# lc202. 快乐数简单

题目描述

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
1
2
3
4
5
6
7

示例 2：

输入：n = 2
输出：false
1
2

思路一

采用哈希表

var isHappy = function(n) {
  const getNext = (n) => {
    return n.toString().split("").map( i => i**2).reduce((a,b) => a+b)
  }
  const map = new Map()
  while(n !== 1) {
    map.set(n, 1)
    n = getNext(n)
    if(map.has(n)) return false
  }
  return true
};
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度:O(n) 空间复杂度:O(n)

思路二

采用快慢指针

var isHappy = function(n) {
  const getNext = (n) => {
    return n.toString().split("").map( i => i**2).reduce((a,b) => a+b)
  }
  let slow = n, fast = getNext(n)
    while(fast !== slow && fast !== 1){
        fast = getNext(getNext(fast));
        slow = getNext(slow);
    }
    return fast == 1

};
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度:O(n) 空间复杂度:O(1)

# lc49. 字母异位词分组中等

题目描述

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
1
2

示例 2:

输入: strs = [""]
输出: [[""]]
1
2

示例 3:

输入: strs = ["a"]
输出: [["a"]]
1
2

思路

异位词的单词组成都一样的

var groupAnagrams = function(strs) {
  const map = new Map()
  const res = []
  for(let i = 0; i < strs.length; i++) {
    const s = strs[i].split('').sort().join('')
    if(!map.has(s)) map.set(s, [strs[i]])
    else map.get(s).push(strs[i])
  }
  for(let [key, val] of map) {
    res.push(val)
  }
  return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13

# lc227. 基本计算器 II中等

题目描述

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

示例 1：

输入：s = "3+2*2"
输出：7
1
2

示例 2：

输入：s = " 3/2 "
输出：1
1
2

示例 3：

输入：s = " 3+5 / 2 "
输出：5
1
2

思路

var calculate = function (s) {
  // 分别存储未计算的数字及符号
  const nums = [],
    operators = [];
  const numReg = new RegExp(/[0-9]/);

  /** 用于将nums最后得两个数根据 operators 最后一个符号作运算，将结果存入 nums */
  const calculator = (nums, operators) => {
    const b = nums.pop();
    const a = nums.pop();
    const op = operators.pop();
    switch (op) {
      case "+":
        nums.push(a + b);
        break;
      case "-":
        nums.push(a - b);
        break;
      case "*":
        nums.push(a * b);
        break;
      case "/":
        nums.push(parseInt(a / b));
        break;
    }
  };

  for (let i = 0; i < s.length; i++) {
    if (s[i] === " ") {
      continue;
    }
    if (numReg.test(s[i])) {
      // 若为数字且数字的长度与操作符长度相同，下一个必定是单独的数字
      if (nums.length === operators.length) {
        nums.push(+s[i]);
      } else {
        // 若数字长度与操作符长度不符，下一个数字字符为前一个数字的一部分。
        nums.push(nums.pop() * 10 + +s[i]);
      }
    } else {
      // 若为低优先级运算符，则先将前面的所有运算结算。
      if (s[i] === "+" || s[i] === "-") {
        while (operators.length > 0) {
          calculator(nums, operators);
        }
      } else {
        // 若为高优先级运算符，则如果前一运算符也是高优先级运算符，先计算之前的数字。
        // 因同一优先级运算须从左到右运算，若最后从右往左算结果会有问题。
        const op = operators[operators.length - 1];
        if (op === "*" || op === "/") {
          calculator(nums, operators);
        }
      }
      operators.push(s[i]);
    }
  }
  // 最后如有未计算的运算符
  while (operators.length > 0) {
    calculator(nums, operators);
  }
  return nums[0];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

# lc190. 颠倒二进制位简单

题目描述

颠倒给定的 32 位无符号整数的二进制位。

提示：

  • 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
  • 在 Java 中，编译器使用二进制补码 (opens new window)记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

示例 1：

输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
1
2
3
4

示例 2：

输入：n = 11111111111111111111111111111101
输出：3221225471 (10111111111111111111111111111111)
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
1
2
3
4

思路

// 常规
var reverseBits = function(n) {
  return parseInt(n.toString(2).padStart(32, 0).split('').reverse().join(''), 2)   
};

// 位运算
var reverseBits = function(n) {
    let ans=0;
    for (let i=0;i<32;i++) {
        ans<<=1;//左移
        ans+=n&1;//加n的最低位
        n>>=1;//n右移
    }
    return ans>>>0; 
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# lc394. 字符串解码中等hot

题目描述

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"
1
2

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"
1
2

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
1
2

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
1
2
var decodeString = function(S) {
  if (!S) {
    return '';
  }
  let stack = [];

  // 存字母前的数字，可能有多位
  let numstr = '';

  for (let s of S) {
    // 多位数字的处理
    if (Number.isInteger(+s)) {
      numstr += s;
      continue;
    }

    if (numstr) {
      stack.push(+numstr);
      numstr = ''; // 注意置空
    }

    // 不是右括号直接入栈
    if (s != ']') {
      stack.push(s);
      continue;
    }

    // 遇到右括号，需要出栈，直到不等于左括号
    let str = '';
    while (stack.length && stack.slice(-1) != '[') {
      let top = stack.pop();
      top += str;
      str = top;
    }

    // 删掉左括号
    stack.pop();

    // 取得数字
    let count = +stack.pop();

    // 字符拼接对应的次数
    let pushStr = str.repeat(count);  

    stack.push(pushStr);
  }
  return stack.join('');
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

时间复杂度:O(n) n位s的长度

空间复杂度:O(n)

# lc395. 至少有 K 个重复字符的最长子串中等

题目描述

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

示例 1：

输入：s = "aaabb", k = 3
输出：3
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
1
2
3

示例 2：

输入：s = "ababbc", k = 2
输出：5
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
1
2
3

思路：递归

var longestSubstring = function (s, k) {
  if (s.length < k) return 0; //如果s长度小于k，提前退出 返回长度0
  const cache = new Map();
  for (let i = 0; i < s.length; i++) {
    cache.set(s[i], cache.has(s[i]) ? cache.get(s[i]) + 1 : 1);
  }
  for (const [key, val] of cache) {
    if (val < k) {
      //数量小于k的字符，那么该字符串必不合格 处理如下
      let res = 0;
      for (const i of s.split(key)) {
        //按照个数小于k的字符划分字符串 分治！
        res = Math.max(res, longestSubstring(i, k)); //对划分的字符串继续递归判断
      }
      return res;
    }
  }
  return s.length; //如果s中所有字符个数都大于k，返回s的长度
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度:O(n)

空间复杂度:O(n ^ n)

# 剑指 Offer 50. 第一个只出现一次的字符简单

题目描述

在字符串 s中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例 1:

输入：s = "abaccdeff"
输出：'b'
1
2

示例 2:

输入：s = "" 
输出：' '
1
2
var firstUniqChar = function(s) {
  for(let i of s) {
    if(s.indexOf(i)===s.lastIndexOf(i)) return i
  }
  return ' '
};
1
2
3
4
5
6

# lc415. 字符串相加简单hot

题目描述

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

示例 1：

输入：num1 = "11", num2 = "123"
输出："134"
1
2

示例 2：

输入：num1 = "456", num2 = "77"
输出："533"
1
2

示例 3：

输入：num1 = "0", num2 = "0"
输出："0"
1
2
var addStrings = function(num1, num2) {
  num1 = num1.split('')
  num2 = num2.split('')
  let carry = 0
  let sum = ''
  while(num1.length || num2.length || carry) {
    let n1 = num1.length ? num1.pop() : 0 
    let n2 = num2.length ? num2.pop() : 0 
    let curSum = (+n1) + (+n2) + carry
    carry = Math.floor(curSum / 10)
    sum = curSum % 10 + sum
  }
  return sum
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 43. 字符串相乘中等hot

题目描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

**注意：**不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"
1
2

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"
1
2

思路

相乘的规律，当我们用 num1[i] * num2[j] 的时候，可能得到两位数，也可能得到一位数，我们都统一算作两位数，高位没有的就用 0 补齐，那么最后我们得到的结果将是一个 i + j 位的数（开头可能存在补齐的 0）。

而我们每次计算 num1[i] * num2[j] 的结果影响到的都是 result 中的 i + j 和 i + j + 1 位。

和加法中逻辑一样，我们将 num1[i] * num2[j] 的结果和 result[i + j + 1] 相加，得到的结果分为 low 和 high 分别存入 result 的 [i + j +1] 和 [i +j] 中。

high 对应的 result[i + j] 可能已经有值了，我们需要将已经存在的值加上。

high 和 result[i +j] 的相加可能存在进位将 high + result[i +j] 的值直接连进位一起保存到 result[i + j] 中。

为什么能这样做呢，因为下次计算 num1[i] * num2[j - 1] 的时候（注意我们是从后往前遍历），会把 result[i + j]和 low 相加，进位自然能被处理，这也是这个算法比较重要的地方

var multiply = function(num1, num2) {
  if(isNaN(num1) || isNaN(num2)) return ''
  if(num1 === '0' || num2 === '0') return '0'
  let len1 = num1.length
  let len2 = num2.length
  const result = []
  for(let i = len1 - 1; i >= 0; i--) {
    for(let j = len2 - 1; j >= 0; j--) {
      let index1 = i + j;
      let index2 = i + j + 1;

      let product = num1[i] * num2[j] + (result[index2] || 0);
      result[index2] = product % 10;
      result[index1] = Math.floor(product / 10) + (result[index1] || 0);
    }
  }
  while(result.length) {
    if(Number(result[0])) break
    else result.shift()
  }
  return result.join('')
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度:O(mn)

空间复杂度:O(m + n)

# lc1360. 日期之间隔几天简单

题目描述

请你编写一个程序来计算两个日期之间隔了多少天。

日期以字符串形式给出，格式为 YYYY-MM-DD，如示例所示。

示例 1：

输入：date1 = "2019-06-29", date2 = "2019-06-30"
输出：1
1
2

示例 2：

输入：date1 = "2020-01-15", date2 = "2019-12-31"
输出：15
1
2

提示：

  • 给定的日期是 1971 年到 2100 年之间的有效日期。
/**
 * @param {string} date1
 * @param {string} date2
 * @return {number}
 */
var daysBetweenDates = function(date1, date2) {
  return Math.abs((+new Date(date1)) - (+new Date(date2))) / (60 * 60 * 1000 * 24)
};
1
2
3
4
5
6
7
8

# lc8. 字符串转换整数 (atoi)简单hot

题目描述

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

  1. 读入字符串并丢弃无用的前导空格
  2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
  3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
  4. 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
  5. 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
  6. 返回整数作为最终结果。

注意：

  • 本题中的空白字符只包括空格字符 ' ' 。
  • 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

示例 1：

输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："42"（读入 "42"）
           ^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。
1
2
3
4
5
6
7
8
9
10
11

示例 2：

输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
            ^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
             ^
第 3 步："   -42"（读入 "42"）
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。
1
2
3
4
5
6
7
8
9
10
11

示例 3：

输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
             ^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。
1
2
3
4
5
6
7
8
9
10
11
var myAtoi = function(s){
    let limit = Math.pow(2,31);
    let num = parseInt(s);

    if(isNaN(num)){
        num = 0;
    }

    if(num < - limit){
        num = -limit;
    }
    if(num > limit - 1){
        num = limit - 1;
    }

    return num;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# KMP算法

# lc28. 实现strStr() 简单

题目描述

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1：

输入：haystack = "hello", needle = "ll"
输出：2
1
2

示例 2：

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

示例 3：

输入：haystack = "", needle = ""
输出：0
1
2

思路：KMP算法

正常的暴力解法是O(m * n),而KMP算法是O(m + n)

直接举例：
 * haystack：   aabaabaafa
 * needle：     aabaaf

 * 
 * needle：
 *  前缀：不包含末尾的所有字符串
 *  后缀：不包含开头的所有字符串
 * 
 * 前缀：               后缀：
 *   a,                  f,
 *   aa,                 af,
 *   aab,                aaf,  
 *   aaba,               baaf,
 *   aabaa,              abaaf,
 *   aabaaf, ❌          aabaaf, ❌           这一行不是前缀也不是后缀
 * 
 * 最长相等的前后缀：
 *   a          0  只有一个，0
 *   aa         1  前缀：a。后缀：a
 *   aab        0  前缀：a、aa。后缀：b、ab。
 *   aaba       1  前缀：a、aa、aab。后缀：a、ba、aba。
 *   aabaa      2  前缀：a、aa、aab、aaba。后缀：a、aa、baa、abaa。
 *   aabaaf     0  ....
 *  
 *  next = 【 0,1,0,1,2,0 】，next就是needle的前缀表。
 * 
 *  1. next中的值代表着该子串的最长相等前后缀的长度，
 *  2. 因为数组是从0开始的，该值还表示子串最长相等前后缀的下一项的索引
 * 
 *  例如： next[4] = 2， 其对应的子串是aabaa，前缀和后缀相等的只有a、aa，长度为2。 
 *        needle[2] === b 恰好等于下一项的索引。
 *
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var strStr = function(haystack, needle) {
    let n = haystack.length
    let m = needle.length
    if(m === 0) return 0

    let next = new Array(m).fill(0)
    for(let i = 1, j = 0; i < m; i++){
      // i：当前子串的后缀末尾
      // j：上一项子串最长相等前后缀的下一项 或者 0 ，并且也是 上一项子串最长相等前后缀的长度
        while(j > 0 && needle[i] !== needle[j]){
          // 如果不同，我们要从未匹配好的地方开始继续匹配。
          // 未匹配好的位置是那里呢？ 👇
          // 我们知道 next 数组的值就代表每一次子串匹配好的长度，
          // 因为数组是从0开始的，所以j - 1就指向了上一个子串未匹配好的位置。
          // 当j === 0时，说明要从头开始重新匹配了
            j = next[j - 1]
        }
        if(needle[i] === needle[j]){
            j++
        }
        next[i] = j
    }

    // 搞懂上面的，下面的也就懂了
    for(let i = 0, j = 0; i < n; i++){
        // 如果当前i 和 j不一致，就回退到上一个相等的位置的下一个看看是否匹配
        // 会不断回退，0为回退到边界，当回退到0意味着要重新从头开始匹配
        while(j > 0 && haystack[i] !== needle[j]){
            j = next[j - 1]
        }
        if( haystack[i] === needle[j]){
            j++
        }
        // 当j 和 m 的长度相等时，就说明存在
        if(j === m){
            return i - m + 1
        }
    }
    return -1
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

思路二

也可以用截取字符串的长度来解

var strStr = function (haystack, needle) {
  if (needle === "") return 0
  for (var i = 0; i < haystack.length; i++) {
      if (haystack[i] === needle[0]) {
          if (haystack.substring(i, i + needle.length) === needle) return i;
      }
  }
  return -1
};
1
2
3
4
5
6
7
8
9

#

上次更新: 2022/03/20, 19:40:28
双指针

双指针→

Copyright © 2021-2022 粤ICP备2021165371号