字符串

1. 反转字符串 【简单】

🔗力扣题目链接https://leetcode.cn/problems/reverse-string/description/

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

• 输入：s = ["h","e","l","l","o"]
• 输出：["o","l","l","e","h"]

示例 2：

• 输入：s = ["H","a","n","n","a","h"]
• 输出：["h","a","n","n","a","H"]

补充

数组元素交换位置：可以利用解构赋值实现，[arr[i], arr[j]] = [arr[j], arr[i]]是一种解构赋值语法糖，无需临时变量即可交换两个元素

const arr = [1, 2, 3, 4, 5]
;[arr[0], arr[1]] = [arr[1], arr[0]]
console.log(arr) // [ 2, 1, 3, 4, 5 ]
;[arr[0], arr[2]] = [arr[1], arr[0]]
console.log(arr) // [ 1, 1, 2, 4, 5 ]

效果等同于：

const arr = [1, 2, 3, 4, 5]
let temp = arr[0]
arr[0] = arr[2]
arr[2] = temp
console.log(arr) // [ 3, 2, 1, 4, 5 ]

思路

由题“你必须原地修改输入数组，O(1) 的额外空间解决”，表明算法的空间复杂度要求为 1，也就是对原数组进行操作

代码-单指针法

// 通过首尾替换实现
var reverseString = function (s) {
  const len = s.length
  for (let i = 0; i < len / 2; i++) {
    ;[s[i], s[len - i - 1]] = [s[len - i - 1], s[i]]
  }
  return s
}

代码-双指针法

var reverseString = function (s) {
  let left = 0,
    right = s.length - 1
  while (left < right) {
    ;[s[left], s[right]] = [s[right], s[left]]
    left++
    right--
  }
}

2. 反转字符串 II

🔗力扣题目链接https://leetcode.cn/problems/reverse-string-ii/description/

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2 输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2 输出："bacd"

思路

- 每次循环都增加 2 \* k（一个区间）
- 根据条件去交换位置（这题要用到上一题的互换方法）
- 看似 3 种情况，实则只有两种：（反转前 k 个 和 反转剩余所有）
  1. 正常情况：反转前 k 个
  2. 剩余小于 2k 但大于等于 k：反转前 k 个
  3. 剩余字符小于 k 的情况：反转剩余字符

代码

var reverseStr = function (s, k) {
  // 将字符串转为数组
  s = s.split('')
  const len = s.length
  for (let i = 0; i < len; i += 2 * k) {
    // 根据条件进行交换
    reverse(s, i, Math.min(i + k, len) - 1)
  }
  // 再将数组转为字符串
  return s.join('')
}

// 双指针法
function reverse(s, left, right) {
  while (left < right) {
    const tmp = s[left]
    s[left] = s[right]
    s[right] = tmp
    left++
    right--
  }
}

/**
条件分析：
if (s - i >= k && s - i < 2 * k) {
  // 剩余: < 2k && >= k
  // 和正常情况一样，反转前k个
  reverse(s, i, i + k - 1)
} else if (s - i < k) {
  // 剩余: < k
  reverse(s, i, len - 1)
} else {
  // 正常情况
  reverse(s, i, i + k - 1)
}
 */

3. 找出字符串中第一个匹配项的下标

🔗力扣题目链接https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

给你两个字符串 haystack 和 needle，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1。

示例 1：

输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在 "sadbutsad" 中出现的位置是 0 和 6，第一个匹配项的下标是 0，所以返回 0。

示例 2：

输入：haystack = "leetcode", needle = "leeto" 输出：-1 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1。

思路

思路 1：

- 开启两层循环，外层循环 haystack，i 为 haystack 的索引，内层循环 needle，j 为 needle 的索引。
- 如果 `haystack[i + j] != needle[j]` 就表示匹配失败，结束内层循环，外层继续

思路 2：
也可以外层循环 haystack，判断 haystack[i] 是否等于 needle[0]，如果等于就进入内层循环，判断 haystack[i + j] 是否等于 needle[j]，如果等于就继续，直到 j == needle.length - 1。如果都匹配，返回 i

代码

var strStr = function (haystack, needle) {
  const n = haystack.length
  const m = needle.length
  for (let i = 0; i + m <= n; i++) {
    let flag = true
    for (let j = 0; j < m; j++) {
      if (haystack[i + j] != needle[j]) {
        flag = false
        break
      }
    }
    if (flag) {
      return i
    }
  }
  return -1
}

4. 重复子字符串

🔗力扣题目链接https://leetcode.cn/problems/repeated-substring-pattern/description/

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab" 输出: true 解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba" 输出: false

示例 3:

输入: s = "abcabcabcabc" 输出: true 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

思路

- 定义一个 str 变量存储子串，去枚举所有子串，判断如果子串 repeat 重复次数等于字符串长度，表示字符串由这几个子串构成，则返回 true
- 循环次数：是 `s.length - 1`，而不是 `s.length`，是因为题中说是**一个能“重复”多次的“子串”**，子串的长度必须小于原字符串，否则无法满足“重复”的定义。

代码

/**
 * const str = 'abc';
 * console.log(str.repeat(2)); // 输出 "abcabc"
 */
var repeatedSubstringPattern = function (s) {
  const len = s.length
  let str = ''
  for (let i = 0; i < s.length - 1; i++) {
    str += s[i]
    if (s === str.repeat(Math.floor(len / str.length))) {
      return true
    }
  }
  return false
}

5. 反转字符串中的单词

🔗力扣题目链接https://leetcode.cn/problems/reverse-words-in-a-string/description/

给定一个字符串 s，要求反转字符串中单词的顺序。单词是由非空格字符组成的字符串，s 中使用至少一个空格将单词分隔开。返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意：输入字符串 s 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入: s = "the sky is blue"

输出: "blue is sky the"

示例 2：

输入: s = "hello world "

输出: "world hello"

解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入: s = "a good example"

输出: "example good a"

解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

思路

这道题可以用 js 的写法，就是将字符串转为数组，然后使用`reverse()`方法，再转为字符串。

第二种就是采用双指针，从后向前遍历字符，
1、右端的指针遇到空格跳过，直到单词的末尾，然后将左端的指针指向右端
2、在 2 的基础上，左指针继续向前，直到遇到空格或小于 0 才停下（此时左右指针之间就是单词）
3、把单词添加到结果字符串中，然后把右指针指向左指针，开始下一轮遍历
4、下一轮遍历开始后，如果还有新单词，就给上一个单词后面添加一个空格

代码1

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function (s) {
  s = s
    .split(' ')
    .map((i) => {
      if (i.trim() !== '') {
        return i.trim()
      }
    })
    .filter(Boolean)
    .reverse()
  return s.join(' ')
}

代码2: 双指针

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function (s) {
  let r = s.length - 1,
    l = r
  let res = ''

  while (l >= 0) {
    // 去除空格，先找到单词的尾部
    while (s[r] === ' ') {
      r--
    }
    l = r

    // 给上次单词加空格，排除第一次
    if (l >= 0 && res) {
      res += ' '
    }

    // 找到单词的头部
    while (s[l] && s[l] !== ' ') {
      l--
    }

    // 此时l到r之间为单词
    for (let i = l + 1; i <= r; i++) {
      res += s[i]
    }

    // 到下一个单词，指针又为同一个起点
    r = l
  }
  return res
}