C++で文字列内の単語を逆順に並べ替える方法

問題の概要

複数の単語からなる文字列が与えられたとき、その文字列内の単語の並び順を逆にすることを考えます。たとえば、入力文字列が「The quick brown fox jumps over a lazy dog」であれば、出力は「dog lazy a over jumps fox brown quick The」となります。

解き方のアプローチ

この問題は、以下の手順で解くことができます。

• getString() 関数を定義します。引数として文字列 s を受け取り、次のように動作します。

• i := 0、j := s のサイズ − 1 で初期化します。

• s[i] が空白であり、かつ i が s のサイズより小さい間、i を 1 ずつ増やします（先頭の余分な空白を読み飛ばします）。

• j が 0 以上かつ s[j] が空白である間、j を 1 ずつ減らします（末尾の余分な空白を読み飛ばします）。

• ret := 空文字列とします。

• i ≤ j である限り、i を 1 ずつ増やしながら以下を繰り返します。

  • ret のサイズが 0 でなく、ret の末尾の要素が空白であり、かつ s[i] も空白であれば、次の反復へ進みます（連続する空白を 1 つに圧縮します）。

  • そうでなければ、ret := ret + s[i] とします。

• もうひとつのメソッド reverseWords() を定義します。こちらも文字列 s を引数として受け取ります。

• j := 0 とします。

• i を 0 から s のサイズ − 1 まで、各ステップで i := j として以下を繰り返します。

  • s[i] が空白であれば、j := i + 1 とします。

  • 空白でなければ、次の処理を行います。

    • j + 1 が s のサイズ未満かつ s[j + 1] が空白でない間、j を 1 ずつ増やします（単語の終端を見つけます）。

    • x := i、y := j とします。

    • x < y である限り、s[x] と s[y] を交換し、x を 1 増やし、y を 1 減らします（単語をその場で反転します）。

    • j を 1 増やします。

• main メソッドでは、以下を実行します。

• まず文字列 s 全体を反転します。

• reverseWords(s) を呼び出します。

• getString(s) を返します。

アルゴリズムのポイント

手順だけ見ると複雑に感じられますが、この手法の核心はとてもシンプルです。まず文字列全体を反転すると、単語の並び順は目的どおり逆になりますが、同時に各単語の中身まで逆向きになってしまいます。そこで次に、各単語ごとにもう一度反転を行うことで、単語の中身を正しい向きに戻します。最後に getString() によって文字列の前後にある余分な空白を取り除き、文中の連続した空白を 1 つにまとめて整形した結果を返します。

C++ 実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string reverseWords(string s) {
      reverse(s.begin(), s.end());
      reverseWordss(s);
      return getString(s);
   }
   string getString(string s){
      int i = 0;
      int j = s.size() - 1;
      while(s[i] == ' ' && i < s.size()) i++;
      while(j >= 0 && s[j] == ' ') j--;
      string ret = "";
      for(;i <= j; i++){
         if(ret.size() && ret.back() == ' ' && s[i] == ' ')continue;
         ret += s[i];
      }
      return ret;
   }
   void reverseWordss(string& s){
      int j = 0;
      for(int i = 0; i < s.size() ;i = j){
         if(s[i] == ' '){
            j = i + 1;
         }
         else{
            while(j + 1 < s.size() && s[j + 1] != ' ') j++;
            int x = i;
            int y = j;
            while(x < y){
               swap(s[x], s[y]);
               x++;
               y--;
            }
            j++;
         }
      }
   }
};
main(){
   Solution ob;
   cout << (ob.reverseWords("The quick brown fox jumps over a lazy dog"));
}

入力

"The quick brown fox jumps over a lazy dog"

出力

"dog lazy a over jumps fox brown quick The"

計算量について見てみましょう。文字列の長さを n とすると、全体の反転も各単語の反転もそれぞれ線形時間で行われるため、時間計算量は O(n) です。reverseWords 内の単語反転は文字列を直接書き換えるインプレース処理ですが、getString で結果用の新しい文字列を組み立てるため、追加で必要な空間計算量は O(n) となります。