题目链接：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”.

Update (2015-02-12):

For C programmers: Try to solve it in-place in O(1) space.

Clarification:

  • What constitutes a word? A sequence of non-space characters constitutes a word.
  • Could the input string contain leading or trailing spaces? Yes. However, your reversed string should not contain leading or trailing spaces.
  • How about multiple spaces between two words? Reduce them to a single space in the reversed string.

这道题的要求是将句子（字符串）中的单词反转。没有空格分隔的就是单词，单词间靠空格分隔。输入可能包含前导或尾随空格，但是反转后不应该包含前导或尾随空格。两个单词间可能有多个空格，但是反转后只保留一个间隔的空格。

  1. istringstream

要格式化多个空格分隔的字符串，首先想到的就是用istringstream，可以省却很多麻烦。

C++引入了ostringstream、istringstream、stringstream这三个类，要使用他们创建对象就必须包含sstream.h头文件。istringstream类用于执行C++风格的串流的输入操作。istringstream可以绑定一个字符串，然后用空格将它们分割开来。

可以看到，代码十分简短。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution
{
public:
    void reverseWords(string &s)
    {
        istringstream is(s);
        s = "";
        is >> s;
        
        string word;
        while(is >> word)
            s = word + " " + s;
    }
};

  1. reverse

假设反转”abc def”中的单词，可以先反转整个字符串，结果为”fed cba”，接着反转字符串中的每个单词，结果为”def abc”。这样就实现了单词反转。

在反转前，需要对字符串进行格式化处理：删除前导和尾随空格，以及删除多个分隔空格只保留一个。接下来，就可以对字符串进行反转以及每个单词进行反转。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution
{
public:
    void reverseWords(string &s)
    {
        formatWords(s);
        reverse(s.begin(), s.end());
        auto it1 = s.begin(), it2 = s.begin();
        while(it2 != s.end())
            if(*it2 == ' ')
            {
                reverse(it1, it2);
                it1 = ++ it2;
            }
            else
                ++ it2;
        reverse(it1, it2);
    }
private:
    void formatWords(string &s)
    {
        int b = 0, e = s.size() - 1, i = 0;
        for( ; b <= e && s[b] == ' '; ++ b);
        for( ; b <= e && s[e] == ' '; -- e);
        while(b <= e)
            if(s[b] != ' ')
                s[i ++] = s[b ++];
            else if(s[++ b] != ' ')
                s[i ++] = ' ';
        s = s.substr(0, i);
    }
};

当然，也可以一边对单词进行反转，一边格式化字符串。代码缩短了好多。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution
{
public:
    void reverseWords(string &s)
    {
        reverse(s.begin(), s.end());
        int e = 0;
        for(int i = 0; i < s.size(); ++ i)
            if(s[i] != ' ')
            {
                if(e != 0)
                    s[e ++] = ' ';
                int j = i;
                while(j < s.size() && s[j] != ' ')
                    s[e ++] = s[j ++];
                reverse(s.begin() + e - (j - i), s.begin() + e);
                i = j;
            }
        s.erase(s.begin() + e, s.end());
    }
};