C++で文字列内の単語を反転する方法（Reverse Words in a String II）

1つの文字型配列（文字列）が入力として与えられたとき、その文字列を「単語ごと」に反転する問題を考えてみましょう。ここでの反転とは、単語同士の出現順序を逆にする操作を指します。

例えば、入力が ['t','h','e',' ','m','a','n',' ','i','s',' ','n','i','c','e']（"the man is nice"）である場合、出力は ['n','i','c','e',' ','i','s',' ','m','a','n',' ','t','h','e']（"nice is man the"）となります。

解法のアプローチ

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

1. まず、配列 s 全体を反転します。
2. 変数 j を 0 で初期化します。
3. n に配列 s のサイズを代入します。
4. i を 0 から n-1 まで 1 ずつ増やしながらループ処理を行います。
   • s[i] が空白文字 ' ' と一致した場合：
     • インデックス j から i の直前までの範囲を反転します。
     • j に i + 1 を代入します。
5. 最後に、インデックス j から n までの範囲を反転します。

このアルゴリズムのポイント

この手法の鍵は「2段階の反転」にあります。まず配列全体を反転すると、単語の並び順は逆になりますが、同時に各単語の中の文字も逆になってしまいます。そこで続いて、空白文字を目印に各単語ごとにもう一度反転を行うことで、単語内部の文字の並びを元に戻します。その結果、「単語の順序だけが逆になった文字列」を得ることができます。

この方法なら、計算量は O(n)、追加のメモリは O(1) で済むため、非常に効率的です。入力配列を直接書き換えるインプレース処理となっている点も特徴です。

実装例

それでは、理解を深めるために実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<char> 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]

※ 出力表示上、空白文字は空欄として表示されています。実際には各単語の間に空白文字が保持された状態で、単語の順序のみが反転されています。