数据结构与算法之栈: LeetCode 151. 反转字符串中的单词 (Ts版)

反转字符串中的单词

• https://leetcode.cn/problems/reverse-words-in-a-string/

描述

• 给你一个字符串 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"

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

提示

• 1 <= s.length <= $10^4$

• s 包含英文大小写字母、数字和空格 ’ ’

• s 中 至少存在一个 单词

• 进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法

Typescript 版算法实现

1 ) 方案1: 使用语言特性

function reverseWords(s: string): string {return s.trim().split(/\s+/).reverse().join(' ');
};

2 ) 方案2: 自行编写对应的函数

function trimSpaces(s: string): string[] {let left = 0, right = s.length - 1;// 去掉字符串开头的空白字符while (left <= right && s[left] === ' ') {left++;}// 去掉字符串末尾的空白字符while (left <= right && s[right] === ' ') {right--;}// 将字符串间多余的空白字符去除const output: string[] = [];while (left <= right) {if (s[left] !== ' ') {output.push(s[left]);} else if (output.length > 0 && output[output.length - 1] !== ' ') {output.push(s[left]);}left++;}return output;
}function reverse(l: string[], left: number, right: number): void {while (left < right) {[l[left], l[right]] = [l[right], l[left]];left++;right--;}
}function reverseEachWord(l: string[]): void {const n = l.length;let start = 0, end = 0;while (start < n) {// 循环至单词的末尾while (end < n && l[end] !== ' ') {end++;}// 翻转单词reverse(l, start, end - 1);// 更新start，去找下一个单词start = end + 1;end = start;}
}function reverseWords(s: string): string {const l = trimSpaces(s);// 翻转字符串reverse(l, 0, l.length - 1);// 翻转每个单词reverseEachWord(l);return l.join('');
}

3 ) 方案3: 双端队列

function reverseWords(s: string): string {let left = 0, right = s.length - 1;// 去掉字符串开头的空白字符while (left <= right && s[left] === ' ') {left++;}// 去掉字符串末尾的空白字符while (left <= right && s[right] === ' ') {right--;}const words: string[] = [];let word: string[] = [];// 将单词 push 到数组中while (left <= right) {if (s[left] === ' ' && word.length > 0) {words.unshift(word.join(''));word = [];} else if (s[left] !== ' ') {word.push(s[left]);}left++;}// 添加最后一个单词if (word.length > 0) {words.unshift(word.join(''));}return words.join(' ');
}