博文中会简要介绍Leetcode P0151题目分析及解题思路。
“Reverse Words in a String”是一道中等难度的题目，解题策略中会运用到栈结构。这道题相对于它的姊妹题p0186难度上要略大一些，难点主要在于给定的字符串开头，结尾和中间有许多连续的空字符。
Given an input string, reverse the string word by word.
Example 1:
Input: "the sky is blue" Output: "blue is sky the"
这道题的解题策略其实比较简单，基本思路是维护一个字符串变量word。
若当前遇到的是空字符，那么会有两种情况，一种是word也为空串，说明遇到了连续的空字符，跳过即可；第二种情况则是word不为空，此时就是截取到了一段单词了，那么将word压入栈后再置空继续查找。
若当前遇到的不是空字符，那么将字符添加到word的末尾，然后继续向后查找。
最终将得到的字符串栈中的字符串依次出栈，形成结果字符串即可。
以下是Java的题解代码实现。
class Solution {
public String reverseWords(String s) {
int N = s.length();
Deque<String> stack = new LinkedList<>();
StringBuilder word = new StringBuilder();
for (int itr=0; itr<N; ++itr) {
if (s.charAt(itr) == ' ') {
if (word.length() > 0) {
stack.offerFirst(word.toString());
word = new StringBuilder();
}
}
else {
word.append(s.charAt(itr));
}
}
if (word.length() != 0)
stack.offerFirst(word.toString());
StringBuilder words = new StringBuilder();
if (!stack.isEmpty())
words.append(stack.pollFirst());
while (!stack.isEmpty()) {
words.append(" ");
words.append(stack.pollFirst());
}
return words.toString();
}
}
以下是C++的题解代码实现。
class Solution {
public:
string reverseWords(string s) {
int N = s.length();
stack<string> stack;
string word = "";
for (int itr=0; itr<N; ++itr) {
if (s[itr] == ' ') {
if (word.length() > 0) {
stack.push(word);
word = "";
}
}
else {
word += s[itr];
}
}
if (word.length() != 0)
stack.push(word);
string words = "";
if (!stack.empty()) {
words += stack.top();
stack.pop();
}
while (!stack.empty()) {
words += " ";
words += stack.top();
stack.pop();
}
return words;
}
};