剑指58：翻转单词顺序

传送门

nowcoder
leetcode

题目描述

把句子单词的顺序翻转。如：”student. a am I” - > “I am a student.”

C++ 代码 - nowcoder

/*
    "Cxx. Bxx Axx"

    reverse("Cxx.") -> ".xxC"
    reverse("Bxx")  -> "xxB"
    reverse("Axx")  -> "xxA"
    reverse(".xxC xxB xxA") -> "Axx Bxx Cxx."

    分割单词，先翻转每一个单词，然后翻转整个字符串。
*/
class Solution {
public:
    string ReverseSentence(string str) {
        if (str.size() <= 1) return str;

        int n = str.size();
        int i = 0, j = 0;
        while (j <= n) {
            if (j == n || str[j] == ' ') {
                reverse(str, i, j - 1);
                i = j + 1;
            }
            j ++;
        }

        reverse(str, 0, n - 1);
        return str;
    }

    void reverse(string& s, int i, int j) {
        while (i < j) {
            char temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            i ++, j --;
        }
    }
};

C++ 代码 - leetcode

/*
    注意：单词组成的句子，前后都可能有空格。
*/
class Solution {
public:
    string reverseMessage(string s) {
        int n = s.size();
        int i = 0, j = 0, start = 0;
        while (i < n) {
            // 去除多余的空格
            while (i < n && s[i] == ' ') i ++;
            // 填一个空白字符，将 j 移动到下一个单词的开头位置
            if (i < n && j > 0) s[j ++] = ' ';
            start = j;
            // 循环遍历至单词的末尾
            while (i < n && s[i] != ' ') s[j ++] = s[i ++];
            // 反转整个单词 s[start, j)
            reverse(s.begin() + start, s.begin() + j);
        }
        s.resize(j);
        reverse(s.begin(), s.end());
        
        return s;
    }
};