C++で解く「エイリアン辞書」問題 ― トポロジカルソートで文字の順序を求める方法

問題の概要

ある新しい異星人の言語(エイリアン語)がラテン文字を使用しているとします。ただし、文字同士の順序関係は不明です。この言語のルールに従って辞書順にソートされた、空でない単語のリストが与えられるので、この言語における文字の順序を求めてください。

例えば、入力が ["wrt","wrf","er","ett","rftt"] の場合、出力は "wertf" となります。

解法のアプローチ:トポロジカルソート

この問題は、グラフ理論におけるトポロジカルソートを用いることで効率的に解けます。隣接する2つの単語を比較し、最初に異なる文字が現れた位置から文字間の順序関係(有向エッジ)を抽出し、そのグラフに対してトポロジカルソートを実行します。

アルゴリズムの手順

• 各文字の入次数を管理するマップ degree を定義する
• 文字間の依存関係を管理するマップ graph を定義する
• 単語に登場するすべての文字について、入次数を 0 で初期化する
• 隣接する単語ペアを順に比較する
  • 最初に異なる文字 x と y が見つかったら、グラフにエッジ x → y を追加し、degree[y] を 1 増やす
  • それ以降の文字比較には順序の情報が含まれないため、ループを抜ける
• 入次数が 0 の文字をすべてキューに追加する
• キューが空になるまで次を繰り返す
  • キューから文字を取り出し、結果文字列の末尾に追加する
  • その文字が指す隣接文字の入次数を 1 減らし、0 になった文字をキューに追加する
• 結果の文字数が登場した全文字数と一致すればその文字列を返し、一致しない場合(順序関係に循環=矛盾が存在する場合)は空文字列を返す

例の解説

入力 ["wrt","wrf","er","ett","rftt"] に対して、隣接する単語同士を比較すると、次の順序関係が得られます。

• "wrt" と "wrf" の比較 → 3文字目が異なる:t < f
• "wrf" と "er" の比較 → 1文字目が異なる:w < e
• "er" と "ett" の比較 → 2文字目が異なる:r < t
• "ett" と "rftt" の比較 → 1文字目が異なる:e < r

これらの関係を統合すると w → e → r → t → f という一連の順序が導かれ、答えは "wertf" となります。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string alienOrder(vector<string>& words) {
      map<char, int> degree;
      map<char, vector<char> > graph;
      int n = words.size();
      for (int i = 0; i < words.size(); i++) {
         for (int j = 0; j < words[i].size(); j++) {
            degree[words[i][j]] = 0;
         }
      }
      for (int i = 0; i < n - 1; i++) {
         int l = min((int)words[i].size(), (int)words[i + 1].size());
         for (int j = 0; j < l; j++) {
            char x = words[i][j];
            char y = words[i + 1][j];
            if (x != y) {
               graph[x].push_back(y);
               degree[y]++;
               break;
            }
         }
      }
      string ret = "";
      queue<char> q;
      map<char, int>::iterator it = degree.begin();
      while (it != degree.end()) {
         if (it->second == 0) {
            q.push(it->first);
         }
         it++;
      }
      while (!q.empty()) {
         char x = q.front();
         q.pop();
         ret += x;
         vector<char>::iterator sit = graph[x].begin();
         while (sit != graph[x].end()) {
            degree[*sit]--;
            if (degree[*sit] == 0) {
               q.push(*sit);
            }
            sit++;
         }
      }
      return ret.size() == degree.size() ? ret : "";
   }
};
main(){
   Solution ob;
   vector<string> v = {"wrt","wrf","er","ett","rftt"};
   cout <<(ob.alienOrder(v));
}

入力

{"wrt","wrf","er","ett","rftt"}

出力

wertf

計算量の分析

• 時間計算量: O(C) — C はすべての単語に含まれる文字の総数です。
• 空間計算量: O(1) — 使用される文字がラテン文字(最大26種)に限られるため、グラフやマップのサイズは実質的に定数とみなせます。