跳至主要內容

151. 反转字符串中的单词


151. 反转字符串中的单词

🟠   🔖  双指针 字符串  🔗 力扣open in new window LeetCodeopen in new window

题目

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(' ');
};

相关题目

题号标题题解标签难度力扣
186反转字符串中的单词 II 🔒双指针 字符串🟠🀄️open in new window 🔗open in new window