题目

给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: “the sky is blue”
输出: “blue is sky the”
示例 2：
输入: “ hello world! “
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

思路

我的想法（栈）

试了一下自己先做，居然只要三次就通过啦！！
这道题一定要审题！
输入的字符串可以有各种各样的空格，但输出的字符串每个单词间只有一个空格且首位都没有空格。
我的思路是用栈来存每个单词，通过找到空格来结束一个单词的存储。
为了避免存入空格，要加上对每个单词长度的判断，如果是0就不能入栈。

  1. class Solution {
  2. public:
  3.     string reverseWords(string s) {
  4.         stack<string> stackstring;
  6.         string a;
  7.         for(int i=0;i<s.length();i++){         
  8.             if(s[i]!=' '){
  9.                 a.insert(a.end(),s[i]);
  10.             }else if(s[i]==' '&& a.size()!=0){  //避免存入空格
  11.                 stackstring.push(a);
  12.                 a.clear();
  13.             }
  14.         }
  15.         if(a.size()!=0){
  16.             stackstring.push(a); //最后一个单词(避免存入空格)
  17.         }
  20.         string result;
  21.         int num =stackstring.size();
  22.         for(int i=0;i<num;i++){
  23.             string temp =stackstring.top();
  24.             stackstring.pop();
  25.             result += temp;
  26.             if(i!= num-1){
  27.                 result +=" "; //最后一个单词后不能有空格
  28.             }
  30.         }
  32.         return result;
  34.     }
  35. };

大佬想法（不用辅助空间，O（1））

  • 移除多余空格
  • 将整个字符串反转
  • 将每个单词反转

也就是先整体反转再局部反转

纯API方法

这个不适合在C++里实现，在java/python里一行魔法
就是split+reverse+[:,:-1]啥的。
但在C++中string没有直接的split函数