LeetCode151—Reverse Words in a String-蒲公英云

LeetCode151—Reverse Words in a String

原题

原题链接

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue”,
return “blue is sky the”.

分析

两次翻转，句子要翻转，句子里的单词也要翻转。

此题还有一些陷阱，比如前后导的空格，单词中间多余的空格等等。

其实有个比较简单的做法是用stringstream，把句子中的单词保存到vector里面，然后将vector中的每个单词逆序，最后再从后往前拼接起来。这个办法有点像java中trim和split，很可惜好像C++并没有这样的函数，只能麻烦一点的做了。

不过还有一个更加朴素的办法：
1.处理空格（前后导和中间多余）
2.字符串逆序
3.字符串中单词逆序

思路差不多，写起来可能会麻烦一点，尤其是处理空格那一部分。

代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
private:
    bool flag;
    void removeSpace(string &s)
    {
        int i=0;
        int j=s.size()-1;
        while(s[i]==' ')
        {
            ++i;
        }
        while(s[j]==' ')
        {
            --j;
        }
        if(i>=s.size())
        {
            flag=true;
            return;
        }
        string tmp(s.begin()+i,s.end()-(s.size()-j)+1);
        s=tmp;
        for(int k=0;k<s.size();k++)
        {
            if(s[k]==' ')
            {
                int t=k+1;
                while(s[t]==' ')
                {
                    s.erase(s.begin()+t);
                }
            //    k=t;
            }
        }
    }
    void reverseSentense(string &s)
    {
        string tmp(s.rbegin(),s.rend());
        s=tmp;
    }
    void reverseWord(string &s)
    {
        int start=0;
        int end;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]==' ')
            {
                end=i-1;
                while(start<end)
                {
                    swap(s[start++],s[end--]);
                }
                start=i+1;
            }
            if(i==s.size()-1)
            {
                end=i;
                while(start<end)
                {
                    swap(s[start++],s[end--]);
                }
            }
        }
    }
public:
    void reverseWords(string &s) {
        flag=false;
        removeSpace(s);
        if(flag)
        {
            string tmp;
            s=tmp;
            return ;
        }
        reverseSentense(s);
        reverseWord(s);
    }
};
int main()
{
    Solution test;
    string s= "   a   b  c d   e  ";
    test.reverseWords(s);
    cout<<s<<endl;
    return 0;
}

——-2016 10/14补充———

使用stringstream分割单词

方法参见：C++ string流简介

class Solution {
    public:
    void reverseWords(string &s) {
      if(s.empty())
        return ;
      stringstream ss(s);
      vector<string> words;
      string word;
      while(ss>>word)
      words.push_back(word+' ');
      if(!words.empty())
      {
          s.clear();
          for(int i=words.size()-1;i>=0;i--)
          {
              s+=words[i];            
          }
          s.pop_back();
      }
      else
      {
          string tmp;
          s=tmp;
      }
    }
};