TNotes.leetcode

Appearance

0557. 反转字符串中的单词 III【简单】

0557. 反转字符串中的单词 III【简单】 ​

1. 📝 题目描述 ​

给定一个字符串 s，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例 1：

txt
输入：s = "Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

示例 2：

txt
输入：s = "Mr Ding"
输出："rM gniD"

提示：

  • 1 <= s.length <= 5 * 10^4
  • s 包含可打印的 ASCII 字符。
  • s 不包含任何开头或结尾空格。
  • s 里 至少 有一个词。
  • s 中的所有单词都用一个空格隔开。

2. 🎯 s.1 - 暴力解法 ​

js
/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function (s) {
  return s
    .split(' ')
    .map((word) => word.split('').reverse().join(''))
    .join(' ')
}

/* 执行流程：
// 1. 先将字符串按照空格进行拆分，得到一个新数组
"Let's take LeetCode contest".split(' ')
// => ["Let's", "take", "LeetCode", "contest"]

// 2. 再对每一项进行反转，在反转过程中，需要将其转为 Array 类型
"Let's take LeetCode contest"
  .split(' ')
  .map((item) => item.split('').reverse().join(''))
// => ["s'teL", 'ekat', 'edoCteeL', 'tsetnoc']

// 3. 最后将结果拼接为一个字符串即可
"Let's take LeetCode contest"
  .split(' ')
  .map((item) => item.split('').reverse().join(''))
  .join(' ')
// => "s'teL ekat edoCteeL tsetnoc" */
  • 时间复杂度：O(n)，遍历字符串并反转每个单词
  • 空间复杂度：O(n)，存储分割后的单词数组

算法思路：

  • 用空格分割字符串得到单词数组
  • 对每个单词进行字符级别的反转
  • 将反转后的单词用空格拼接成新字符串
  • 上述这些基本步骤可以使用语言内置的 API 来辅助完成

3. 🎯 s.2 - 双指针原地交换 ​

js
/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function (s) {
  let result = ''
  let start = 0

  for (let i = 0; i <= s.length; i++) {
    if (i === s.length || s[i] === ' ') {
      // 反转当前单词
      for (let j = i - 1; j >= start; j--) {
        result += s[j]
      }
      if (i < s.length) result += ' '
      start = i + 1
    }
  }

  return result
}
  • 时间复杂度：O(n)，遍历字符串的每个字符一次
  • 空间复杂度：O(n)，需要构建结果字符串

算法思路：

  • 使用双指针标记每个单词的起始和结束位置
  • 遇到空格或字符串末尾时，从后向前遍历当前单词并追加到结果字符串
  • 相比 s.1，避免了数组分割和额外的字符串操作，更加直接

Discussions