151. 反转字符串中的单词

🟠   🔖  双指针 字符串  🔗 力扣 LeetCode

题目

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"

Output: "blue is sky the"

Example 2:

Input: s = " hello world "

Output: "world hello"

Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good example"

Output: "example good a"

Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints:

• 1 <= s.length <= 10^4
• s contains English letters (upper-case and lower-case), digits, and spaces ' '.
• There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

题目大意

给定一个字符串，逐个翻转字符串中的每个单词。

说明：

• 无空格字符构成一个单词。
• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

请尝试使用 O(1) 额外空间复杂度的 原地 解法。

解题思路

思路一：分割+倒序

常规的方式是把 s 按空格 split 成若干单词，然后 reverse 这些单词的顺序，最后把这些单词 join 成句子。

复杂度分析

• 时间复杂度： O(n)，其中 n 为字符串 s 的长度；
  • split() 方法为 O(n)
  • reverse() 方法为 O(n)
  • filter() 方法为 O(n)
  • join() 方法为 O(n)
• 空间复杂度： O(n)，新建的字符串数组总长度 ≤n ，占用 O(n) 大小的额外空间。

---

思路二：双指针

• 倒序遍历字符串 s ，记录单词左右索引边界 i , j 。
• 每确定一个单词的边界，则将其添加至单词列表 res 。
• 最终，将单词列表拼接为字符串，并返回即可。

复杂度分析

• 时间复杂度： O(n)，其中 n 为字符串 s 的长度；
• 空间复杂度： O(1)

代码

分割+倒序

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

双指针

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function (s) {
	s = s.trim();
	let i = (j = s.length - 1),
		res = '';
	while (i >= 0) {
		while (i >= 0 && s[i] != ' ') {
			i--;
		}
		res += s.slice(i + 1, j + 1);
		while (i >= 0 && s[i] == ' ') {
			i--;
		}
		j = i;
		if (i != -1) {
			res += ' ';
		}
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度
186	反转字符串中的单词 II 🔒		双指针 字符串