C++で文中の単語を長さ順に並べ替える方法

本記事では、C++を用いて文中の単語を長さの昇順に並べ替えるアルゴリズムを解説します。

問題の概要

ある文字列が与えられ、この文字列は「文（センテンス）」と呼ばれるものとします。文は次の形式を満たしています。

• 先頭の文字は必ず大文字である。
• 各単語は1つの半角スペースで区切られている。

求められるのは、文中のすべての単語を長さが短い順（昇順）に並べ替えた新しい文を作ることです。ここで重要なルールとして、同じ長さの単語がある場合は、元の文中での出現順序を維持する必要があります。これはいわゆる「安定なソート（stable sort）」の考え方です。

最終的に、これらのルールを適用した結果の文字列を返します。

入出力例

たとえば、入力が "I love to code in cpp" の場合、各単語の長さは次のようになります。

• I（1文字）、to（2文字）、in（2文字）、cpp（3文字）、love（4文字）、code（4文字）

したがって、出力は "I to in cpp love code" となります。「to」と「in」、「love」と「code」はそれぞれ同じ長さのため、元の順序が保たれている点に注目してください。

解法のアプローチ

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

1. 文の先頭文字を小文字に変換する（ソート後に元に戻すため）。
2. 文をスペースで分割し、単語の配列 x を作成する。
3. (単語, 元のインデックス) のペアを格納する配列 s を用意する。
4. 各単語とそのインデックスをペアとして s に追加していく。
5. s を「単語の長さ」を基準にソートする。長さが同じ場合は「元のインデックス」で比較することで、安定性を保証する。
6. 結果格納用の空文字列 ret を用意し、ソート済みの単語を順番に連結する。単語間にはスペースを挿入する。
7. 最後に ret の先頭文字を大文字に戻して返す。

C++による実装例

それでは、上記の手順を実際のコードで確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   vector <string> split(string& s, char delimiter){
      vector <string> tokens;
      string token;
      istringstream tokenStream(s);
      while(getline(tokenStream, token, delimiter)){
         tokens.push_back(token);
      }
      return tokens;
   }
   static bool cmp(pair <string, int>& a, pair <string, int>& b){
      if(a.first.size() != b.first.size()) return a.first.size() < b.first.size();
         return a.second < b.second;
   }
   string arrangeWords(string text) {
      text[0] += 'a' - 'A';
      vector<string> x = split(text, ' ');
      vector<pair<string, int> > s;
      for (int i = 0; i < x.size(); i++)
      s.push_back({ x[i], i });
      sort(s.begin(), s.end(), cmp);
      string ret = "";
      for (int i = 0; i < s.size(); i++) {
         ret += s[i].first;
         if (i != s.size() - 1)
            ret += ' ';
      }
      ret[0] += 'A' - 'a';
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.arrangeWords("I love to code in cpp"));
}

コードのポイント

• split関数： istringstream と getline を組み合わせることで、指定した区切り文字（ここではスペース）で文字列を簡単に分割できます。
• 比較関数cmp： 単語の長さが異なる場合は長さで比較し、同じ場合はペアに保持しておいた元のインデックスで比較します。これにより、同じ長さの単語の相対的な順序が崩れません。
• 大文字・小文字の処理： ソートの前に先頭文字を小文字化し、完成後に再び大文字へ戻すことで、出力フォーマットの要件を満たしています。

実行結果

入力

"I love to code in cpp"

出力

I to in cpp love code

計算量について

単語数を n、各単語の平均的な長さを考慮すると、ソート部分が支配的となり、時間計算量は O(n log n) となります。また、単語とインデックスを保持するため、空間計算量は O(n) です。文字列の分割と再構築も線形時間で処理できるため、全体として効率的なアルゴリズムと言えます。

まとめ

この問題の鍵となるのは、「同じ長さの単語は元の順序を維持する」という安定性の要件です。(単語, インデックス) のペアを作り、カスタム比較関数でソートすることで、シンプルかつ確実に要件を満たす実装が可能になります。C++では stable_sort を使うという選択肢もありますが、インデックスを明示的に扱うこの手法は、他の言語にも応用しやすい汎用的なパターンです。