Reverse Words in a String (M)
题目
Given an input string, reverse the string word by word.
Example 1:
Input: "the sky is blue"
Output: "blue is sky the"
Example 2:
Input: " hello world! "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
Input: "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.
Note:
- A word is defined as a sequence of non-space characters.
- Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
- You need to reduce multiple spaces between two words to a single space in the reversed string.
题意
将给定字符串中的非空格单词的顺序逆置，要求新字符串中前后无空白字符，且每个单词之间有一个空格。
思路
将字符串中所有单词依次存入栈中，再出栈构建新字符串即可。
代码实现
Java
class Solution {
public String reverseWords(String s) {
s = s.trim();
Deque<String> stack = new ArrayDeque<>();
StringBuilder sb = new StringBuilder();
int first = 0, last = 0;
while (last < s.length()) {
while (last < s.length() && s.charAt(last) != ' ') {
last++;
}
stack.push(s.substring(first, last));
while (last < s.length() && s.charAt(last) == ' ') {
last++;
}
first = last;
}
for (String word : stack) {
if (sb.length() == 0) {
sb.append(word);
} else {
sb.append(" " + word);
}
}
return sb.toString();
}
}
JavaScript
API
/**
* @param {string} s
* @return {string}
*/
var reverseWords = function(s) {
return s.trim().split(/s+/).reverse().join(' ')
};
栈
/**
* @param {string} s
* @return {string}
*/
var reverseWords = function (s) {
s = s.trim()
let word = ''
let stack = []
for (let c of s) {
if (c !== ' ') {
word += c
} else if (word.length !== 0) {
stack.push(word)
word = ''
}
}
if (word.length !== 0) {
stack.push(word)
}
let t = ''
while (stack.length !== 0) {
if (t.length !== 0) {
t += ' '
}
t += stack.pop()
}
return t
}