C++で単語列が昇順ソートとみなせるアルファベット順を見つける方法

問題概要

英小文字からなる単語の配列が与えられたとき、与えられた単語列全体が「昇順にソートされている」とみなせるようなアルファベットの順序(独自の辞書式順序)を1つ見つけます。そのような順序が存在する場合はそれを出力し、存在しない場合は "Impossible" を返します。

例えば、入力が words = ["efgh", "wxyz"] の場合、出力は zyxvutsrqponmlkjihgfewdcba となります。この順序に従えば、「efgh」は「wxyz」より前に来るため、単語列は正しくソートされていることになります。

解き方のアプローチ

この問題は、トポロジカルソート(Kahnのアルゴリズム)を使うことで効率的に解くことができます。基本的な考え方は以下の通りです。

• 隣接する2つの単語を比較し、最初に異なる文字のペアから「pre[j] の文字は s[j] の文字より前に来なければならない」という制約を導きます。
• この制約を有向グラフの辺として構築し、各文字の入次数も記録します。
• 前の単語が後の単語より長い場合(例:「abc」の直後に「ab」)、どのような順序でも成立しないため "Impossible" となります。
• 入次数が0の文字から順に処理していくことで、条件を満たす順序を1つ求めます。

アルゴリズムの手順

• ALPHABET := 26(アルファベットの文字数)とする
• n := 配列 v のサイズとする
• n が 1 の場合は "abcdefghijklmnopqrstuvwxyz" を表示して終了する
• サイズ ALPHABET の隣接リスト adj を定義する
• サイズ ALPHABET の入次数配列 in を 0 で初期化する
• pre := v[0] とする
• i = 1 から n-1 まで以下を繰り返す:
  • s := v[i] とする
  • j = 0 から min(pre の長さ, s の長さ) - 1 まで調べ、s[j] != pre[j] となった時点でループを抜ける
  • 最初に異なる文字が見つかった場合(j < min の長さの場合):
    • adj[pre[j] - 'a'] の末尾に s[j] - 'a' を追加する
    • in[s[j] - 'a'] を 1 増やす
    • pre := s として次の反復へ進む
  • pre の長さが s の長さより大きい場合:
    • "Impossible" を表示して終了する
  • pre := s とする
• スタック my_stack を定義し、in[i] == 0 となるすべての i をプッシュする
• 出力用配列 out と、サイズ26の訪問フラグ配列 vis(false で初期化)を定義する
• スタックが空になるまで以下を繰り返す:
  • x := スタックの先頭要素を取り出して削除する
  • vis[x] := true とし、out の末尾に x + 'a' を追加する
  • adj[x] の各要素について:
    • 訪問済みならスキップする
    • in[adj[x][i]] を 1 減らし、0 になったらスタックにプッシュする
• 未訪問の頂点が残っている場合は循環が存在するため、"Impossible" を表示して終了する
• out の内容を順に出力する

実装例

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

#include <bits/stdc++.h>
using namespace std;
#define ALPHABET 26
void search_ordering(vector<string> v) {
    int n = v.size();
    if (n == 1) {
        cout << "abcdefghijklmnopqrstuvwxyz";
        return;
    }
    vector<int> adj[ALPHABET];
    vector<int> in(ALPHABET, 0);
    string pre = v[0];
    for (int i = 1; i < n; ++i) {
        string s = v[i];
        int j;
        for (j = 0; j < min(pre.length(), s.length()); ++j)
            if (s[j] != pre[j])
                break;
        if (j < min(pre.length(), s.length())) {
            adj[pre[j] - 'a'].push_back(s[j] - 'a');
            in[s[j] - 'a']++;
            pre = s;
            continue;
        }
        if (pre.length() > s.length()) {
            cout << "Impossible";
            return;
        }
        pre = s;
    }
    stack<int> my_stack;
    for (int i = 0; i < ALPHABET; ++i)
        if (in[i] == 0)
            my_stack.push(i);
    vector<char> out;
    bool vis[26];
    memset(vis, false, sizeof(vis));
    while (!my_stack.empty()) {
        char x = my_stack.top();
        my_stack.pop();
        vis[x] = true;
        out.push_back(x + 'a');
        for (int i = 0; i < adj[x].size(); ++i) {
            if (vis[adj[x][i]])
                continue;
            in[adj[x][i]]--;
            if (in[adj[x][i]] == 0)
                my_stack.push(adj[x][i]);
        }
    }
    for (int i = 0; i < ALPHABET; ++i)
    if (!vis[i]) {
        cout << "Impossible";
        return;
    }
    for (int i = 0; i < out.size(); ++i)
    cout << out[i];
}
int main() {
    vector<string> v{"efgh", "wxyz"};
    search_ordering(v);
}

入力

{"efgh", "wxyz"}

出力

zyxvutsrqponmlkjihgfewdcba

まとめ

このアルゴリズムでは、単語間の比較によって得られる文字の優先関係をグラフとして表現し、トポロジカルソートで整合的なアルファベット順を復元しています。計算量は単語数を N、平均的な単語長を L とすると O(N × L + 26) 程度で収まり、非常に効率的です。また、制約に循環が含まれる場合や、プレフィックスの不整合(「abc」の後に「ab」が現れる等)がある場合には "Impossible" を正しく検出できる点もポイントです。