目录
题目
557. 反转字符串中的单词 III - 力扣（LeetCode）
思路一：使用栈
核心思路
栈具有"后进先出"的特性，非常适合用来反转元素顺序。对于这道题，我们可以：
- 遍历字符串的每个字符
- 当遇到非空格字符时，将其压入栈中
- 当遇到空格时，弹出栈中所有字符（此时弹出顺序正好是反转后的单词）
- 将栈空后，添加空格
- 处理最后一个单词（字符串结尾没有空格时）
详细过程
以输入 "Let's take LeetCode contest" 为例：
初始化：
- 创建一个空栈 st
- 创建一个空结果字符串 result
遍历字符串：
- 遇到 'L'：压入栈 -> 栈：[L]
- 遇到 'e'：压入栈 -> 栈：[L, e]
- 遇到 't'：压入栈 -> 栈：[L, e, t]
- 遇到 '''：压入栈 -> 栈：[L, e, t, ']
- 遇到 's'：压入栈 -> 栈：[L, e, t, ', s]
- 遇到 ' '（空格）：
- 弹出栈中所有字符：result = "s'teL"
- 添加空格：result = "s'teL "
- 处理 "take"：
- 压入 't', 'a', 'k', 'e' -> 栈：[t, a, k, e]
- 遇到空格，弹出所有字符：result = "s'teL ekat "
- 处理 "LeetCode"：
- 压入所有字符 -> 栈：[L, e, e, t, C, o, d, e]
- 遇到空格，弹出所有字符：result = "s'teL ekat edoCteeL "
- 处理 "contest"：
- 压入所有字符 -> 栈：[c, o, n, t, e, s, t]
- 没有遇到空格，循环结束
处理最后一个单词：
- 循环结束后，栈中还有字符 -> 栈：[c, o, n, t, e, s, t]
- 弹出所有字符：result = "s'teL ekat edoCteeL tsetnoc"
返回结果："s'teL ekat edoCteeL tsetnoc"
时间和空间复杂度
- 时间复杂度：O(n)，其中n是字符串长度，每个字符最多被操作两次（入栈和出栈）
- 空间复杂度：O(w)，其中w是最长单词的长度（栈的最大大小）
读者可能的错误写法
class Solution {
public:
string reverseWords(string s) {
//利用栈的性质
stack<char> st;
string result = "";
for(int i = 0; i< s.size();i++)
{
if(s[i] != " ")
{
st.push(s[i]);
}
else
{
while(!st.empty())
{
result.push_back(st.top());
st.pop();
}
result.push_back(s[i]);
}
}
return s;
}
};字符比较错误：if(s[i] != " ") 是在比较字符和字符串，应该改为 if(s[i] != ' ')（使用单引号表示字符）
没有处理最后一个单词：如果字符串不以空格结尾，最后一个单词不会被处理
返回原字符串：函数最后返回的是原字符串 s 而不是处理后的 result
空格处理：在 else 分支中，你先弹出栈中的字符，再添加空格，这是正确的
正确写法
class Solution {
public:
string reverseWords(string s) {
//利用栈的性质
stack<char> st;
string result = "";
for(int i = 0; i< s.size();i++)
{
if(s[i] != ' ')
{
st.push(s[i]);
}
else
{
while(!st.empty())
{
result.push_back(st.top());
st.pop();
}
result.push_back(s[i]);
}
}
while(!st.empty()) {
result.push_back(st.top());
st.pop();
}
return result;
}
};错误写法二
class Solution {
public:
string reverseWords(string s) {
for(int i = 0; i< s.size();i++)
{
int start = i;
while(i<s.size() && s[i]!=' ')
{
i++;
}
int left = start;
int right = i-1;
while(left<right)
{
swap(s[left],s[right]);
left++;
right--;
}
if(s[i] == ' ')
{
i++;
}
}
return s;
}
}; 
正确写法二
class Solution {
public:
string reverseWords(string s) {
int n = s.length();
int i = 0;
while (i < n)
{
int start = i;
while(i<s.size() && s[i]!=' ')
{
i++;
}
int left = start;
int right = i-1;
while(left<right)
{
swap(s[left],s[right]);
left++;
right--;
}
while(s[i] == ' ')
{
i++;
}
}
return s;
}
};