C++で文字配列に格納された文の単語順を反転する方法

各要素が1文字として格納された文字配列(文)が入力として与えられたとき、その文を単語ごとに反転することを考えます。

例えば、入力が ["t","h","e"," ","m","a","n"," ","i","s"," ","n","i","c","e"] の場合、出力は ["n","i","c","e"," ","i","s"," ","m","a","n"," ","t","h","e"] となります。つまり、各単語内の文字の並びはそのままに、単語の出現順だけが逆になります。

この問題を解くために、以下の手順に従います。

• 配列 s 全体を反転する
• j := 0 とする
• n := s のサイズとする
• i := 0 から i < n まで、i を1ずつ増やしながら以下を繰り返す
  • s[i] が空白文字 ' ' と等しい場合、以下を行う
    • 配列 s のインデックス j から i までの範囲を反転する
    • j := i + 1 とする
• 最後に、配列 s のインデックス j から n までの範囲を反転する

このアルゴリズムのポイントは、2段階の反転を行う点にあります。まず文字列全体を反転することで単語の並び順を逆にし、その後に空白文字を区切りとして各単語内の文字順を元に戻します。この方法なら、余分な配列を用意することなく in-place(その場)で処理を完了できます。

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

実装例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   void reverseWords(vector<char>& s) {
      reverse(s.begin(), s.end());
      int j = 0;
      int n = s.size();
      for(int i = 0; i < n; i++){
         if(s[i] == ' '){
            reverse(s.begin() + j, s.begin() + i);
            j = i + 1;
         }
      }
      reverse(s.begin() + j, s.begin() + n);
   }
};
main(){
   Solution ob;
   vector<char> v = {'t','h','e',' ','m','a','n',' ','i','s',' ','n','i','c','e'};
   ob.reverseWords(v);
   print_vector(v);
}

入力

{'t','h','e',' ','m','a','n',' ','i','s',' ','n','i','c','e'}

出力

[n, i, c, e,  , i, s,  , m, a, n,  , t, h, e]

計算量の評価

このアルゴリズムの時間計算量は O(n) です。配列全体の反転に O(n)、その後の各単語の反転も合計で O(n) に収まるためです。また、空間計算量は O(1) であり、入力配列を直接書き換えるため、追加のメモリはほとんど必要ありません。大きな文字列を扱う場合でも効率的に動作する、実用的なアプローチと言えます。