LeetCode(151) 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.
click to show clarification.
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.
ぶんせき
単語単位で文字列を反転する文字列を与え、空間的複雑度をO(1)とする.
追加の要件:

単語の間には最大1つのスペースしかありません.余分なスペースは削除します.

文字列の先頭と末尾に余分なスペースを追加できません.

方法1:この問題の簡単な解法はvectorを借りて、文字列の単語を順番に容器に入れて、それから直接容器を反転して、メタ文字列を更新すればいいが、この方法は空間の複雑さの要求に合わない.
方法2:2つのステップで解決し、まず、文字列全体を反転し、それから前から後ろに遍歴し、1つの単語を通過するたびに、その単語を反転します.もちろん、プロセスでは、余分なスペースの問題を合理的に処理する必要があります.詳細はコードを参照してください.
ACコード

class Solution {
public:
    void reverseWords(string &s) {
        if (s.empty())
            return;

        //  ，       
        reverse(s.begin(), s.end());

        int n = s.size();

        //       ,         ，             ，             （    ）
        string tmp = s;
        s.clear();
        //       ,          
        bool flag = true;
        for (int i = 0; i < n;)
        {       
            //        
            if (tmp[i] == ' ')
            {
                ++i;
                continue;
            }//if

            string::iterator beg = tmp.begin() + i, end = tmp.begin();

            for (int j = i; j < n; ++j)
            {               
                //                     
                if (tmp[j] == ' ')
                {
                    end += j;

                    reverse(beg, end);
                    //           
                    if (flag)
                    {
                        s = s + tmp.substr(i, j - i);
                        flag = false;
                    }
                    else{
                        s = s + " " + tmp.substr(i, j - i);
                    }

                    i = j + 1;
                    break;
                }//if

                if (j == n - 1)
                {
                    reverse(beg, tmp.end());
                    if (flag)
                    {
                        s = s + tmp.substr(i, j - i + 1);
                    }
                    else{
                        s = s + " " + tmp.substr(i, j - i + 1);
                    }
                    i = j + 1;
                    break;
                }
            }//for
        }//for
    }
};

GitHubテストプログラムソースコード