翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。

说明：

• 无空格字符构成一个单词。
• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

解题思路:

方法一：

1) 翻转整个句子
2) 翻转句中单词
3) 删除多余的空格

方法二：字符流，用stringstream来做

时间复杂度

O(n)

空间复杂度

O(1)

代码

方法一

class Solution {
public:
    void Reverse(string &s,int start,int end)
    {
        while(start<end)
        {
            swap(s[start++],s[end--]);
        }
    }
    
    void cleanSpaces(string &s)
    {
        int n = s.size();
        int i=0,j=0;
        while(j<n)
        {
            while(j<n && s[j] == ' ') j++; // 跳过空格
            while(j<n && s[j] != ' ')s[i++] = s[j++]; 
            // 保留单词（非空格部分）
            while(j<n && s[j] == ' ') j++; 
            // 跳过空格（主要是防止结尾有空格，然后再添加空格越界）
            if (j<n) s[i++] = ' '; // 补充空格
        }
        s = s.substr(0,i); // 改成引用减少一次拷贝
    }

    string reverseWords(string s) 
    {
        int n = s.size();
        //翻转整个语句
        Reverse(s,0,n-1);
        // 翻转句中单词
        int start = 0, end = 0;
        int i=0;
        while(i<n)
        {
            while(i<n && s[i]==' ') i++;
            start = end = i;
            while(i<n && s[i]!=' ')
            {
                i++;
                end++;
            }
            Reverse(s,start,end-1);
        }
        //清除多余空格
        s = cleanSpaces(s);
        return s;
    }
};

方法二：字符流

class Solution {
public:
    string reverseWords(string s) {
        stringstream ss;
        string ans="",temp;
        ss<<s;
        while(ss>>temp){
            ans=" "+temp+ans;
        }
        if(ans!="")
            ans.erase(ans.begin());
        return ans; 
    }
};

参考

• C++ 学习笔记之——字符串和字符串流
• C++ string 类中substr的使用方法