設問と適用コンテキスト
空でない小文字 ASCII 文字列の配列 words が与えられ、この配列が未知のアルファベット順によってソートされていると主張されていると仮定します。入力に含まれるすべての異なる文字をちょうど1回ずつ含み、単語リストがソートされた状態となる任意の順序を返してください。そのような順序が存在しない場合は、空文字列を返してください。複数のアルファベットが成立する場合は、そのうちのいずれか1つで構いません。
面接向けのバージョンでは、最大 10,000 単語、全体で最大 100,000 文字を想定します。これらは演習上の制約であり、特定のプラットフォームの制限ではありません。["wrt", "wrf", "er", "ett", "rftt"] に対する1つの回答は "wertf" です。リスト ["abc", "ab"] は、より長い単語が自身の接頭辞の前に現れているため不可能です。リスト ["z", "x", "z"] は、z < x と x < z の両方を意味するため不可能です。
難しい部分はトポロジカルソートの前にあります。入力としてソート済みの単語が与えられるため、グラフのエッジを推論する必要があります。正しい解法は、辞書順比較によって正当化される制約のみを正確に推論し、エッジを持たない文字を保持し、無効な接頭辞と有向閉路を区別しなければなりません。
面接官が評価するポイント
第1のシグナルは、候補者が隣接する2つの単語の最初の異なる文字からエッジを導出しているかどうかです。"wrt" が "wrf" より前に現れる場合、その比較によって t < f が証明されます。最初の不一致より後の文字は、辞書順比較がすでに決定しているため、このペアについて何も明らかにしません。
第2のシグナルは、接頭辞の推論です。比較されたすべての文字が一致する場合、短い単語が先に来る必要があります。"abc" の前の "ab" はエッジを追加せず、有効なままです。"ab" の前の "abc" は、考えられるすべてのアルファベットと矛盾します。トポロジカルソート単体ではエッジが作成されないため、この矛盾を発見することはできません。
第3のシグナルは、完全なグラフ構築です。単一単語の入力による孤立した文字を含め、観察されたすべての文字にノードが必要です。同じエッジの重複した根拠によって入次数を2回増やしてはなりません。送信元ノードごとにセット（集合）を持つことで、隣接リストと入次数の整合性が保たれます。
最後のシグナルは、証明と検証です。カーンのアルゴリズム（Kahn's algorithm）は、すべてのノードを削除した場合にのみ完全な順序を返します。出力が短い場合は閉路が残っていることを証明します。入次数が 0 の選択肢が複数あることは、根拠が一意のアルファベットを決定しないことを意味します。これは基本契約のもとで有効であり、エラーとして誤認してはなりません。
回答前に明確にすべき質問
- 入力にはアルファベットのすべての文字が含まれていますか？ この回答は、単語内で観察された各文字を順序付けます。外部のアルファベット定義なしに、出現しない文字を創作したり配置したりすることはできません。
- 任意の有効な順序で受け入れられますか？ 基本問題はいずれも受け入れます。ホスト言語の文字順で最小の結果を要求する場合は最小ヒープが必要となり、計算量が変わります。
- 不可能性はどのように表現すべきですか？ この契約では、無効な接頭辞と閉路の両方に対して空文字列を使用します。本番環境の API では、構造化された理由と証拠（witness）を返す場合があります。
- 文字とは何ですか？ 基本入力には小文字の ASCII 文字が含まれます。Unicode コードポイントや書記素クラスタの場合は、グラフ構築の前にトークン化の契約が必要です。
- 単語は重複してもよいですか？ はい。同一の隣接単語は制約を追加しません。辞書が無効になることもありません。
- アルファベットは一意である必要がありますか？ いいえ。フォローアップでは、各ステップで利用可能な入次数 0 のノードの数を確認することで一意性を検出できます。
- 入力が空になることはありますか？ このバージョンでは、少なくとも1つの空でない単語が必要です。空の入力が許可される場合は、期待される結果が空のアルファベットなのか無効なリクエストなのかを確認してください。
30秒の回答フレームワーク
「重複のない文字ごとにグラフノードを作成します。隣接する各単語ペアについて、最初の不一致まで走査します。これにより、前の単語の文字から後の単語の文字への有向エッジが1つ得られます。不一致がなく、前の単語の方が長い場合、接頭辞の順序として不可能なため、空文字列を返します。入次数を維持しながらエッジの重複を排除し、入次数が 0 のすべての文字からカーンのトポロジカルソートを実行します。すべてのノードを処理できれば、結果は推論されたすべての比較を満たします。処理されたノード数が少なければ、閉路によって辞書が矛盾しています。全体の計算時間は入力文字数にグラフを加えた線形時間であり、複数の有効なトポロジカル順序が許容されます。」
ステップごとの詳細解説
全単語にわたる総文字数を C、異なる文字の数を U、重複のない優先順位エッジの数を E とします。遭遇したすべての文字に対して、graph[ch] をセットとして、indegree[ch] を 0 として初期化します。この初期化は単語を比較する前に行う必要があります。文字が有効で制約がない場合もあるため、エッジの端点だけではノード集合を定義できません。
隣接する単語のみを比較します。隣接ペアがすべてソートされていることを証明すれば、推移律によってリスト全体がソートされていることが証明されるため、隣接比較だけで十分です。また、単語ペアの比較回数が2乗に膨らむのを防ぐことができます。ペア first と second について、短い方の長さまで一致する位置を検査します。
- 最初の不一致
first[i] != second[i]で、first[i] -> second[i]を追加し、そのペアの比較を終了します。 - 共有するすべての位置が一致し、
firstの方が長い場合は、空文字列を返します。 - 共有するすべての位置が一致し、
firstの方が長くなければ、エッジを追加しません。
新しく挿入されたエッジのみが宛先の入次数を増やします。"za" < "zb" と "ca" < "cb" の両方が a -> b を意味すると仮定します。そのエッジを2回カウントすると、a が削除された後も b に正の入次数が残り、誤って閉路と判定されてしまいます。
カーンのアルゴリズムは、入次数が 0 のすべての文字をキューに入れます。その不変条件は次の通りです。未処理の文字ごとに、入次数は他の未処理文字からの入力エッジの数と等しく、キューにはそのような先行ノードを持たない文字が正確に含まれます。キューに入った文字を取り出すことは安全です。各出力隣接ノードをデクリメントすることでそれらのエッジの削除をモデル化し、隣接ノードは最後の未解消の先行ノードが消えたときにキューに入ります。
from collections import deque
def alien_order(words: list[str]) -> str:
graph = {char: set() for word in words for char in word}
indegree = {char: 0 for char in graph}
for first, second in zip(words, words[1:]):
limit = min(len(first), len(second))
for index in range(limit):
before = first[index]
after = second[index]
if before == after:
continue
if after not in graph[before]:
graph[before].add(after)
indegree[after] += 1
break
else:
if len(first) > len(second):
return ""
ready = deque(
char for char, degree in indegree.items() if degree == 0
)
order: list[str] = []
while ready:
char = ready.popleft()
order.append(char)
for neighbor in graph[char]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
ready.append(neighbor)
return "".join(order) if len(order) == len(indegree) else ""証明には2つの層があります。第1に、グラフ抽出が健全であることです。すべてのエッジは隣接ペアの最初の不一致から生じるため、すべての有効なアルファベットはそれを尊重しなければなりません。接頭辞チェックにより、不一致が存在しないにもかかわらず順序付けが不可能な唯一の隣接ケースが除外されます。第2に、トポロジカルソートが健全であることです。キューの不変条件により、出力されるすべての文字が推論されたすべての先行ノードの後に現れることが保証されます。したがって、隣接する各単語ペアが順序付けられ、リスト全体が順序付けられます。
アルゴリズムが出力する文字数が U 未満の場合、残りのすべてのノードは正の入次数を持ちます。残りの任意のノードから開始して入力エッジを繰り返し辿ると、有限グラフ内では必ずノードを再訪することになります。その繰り返される区間が有向閉路です。どのような線形アルファベットもその閉路を満たすことはできません。逆に、非巡回グラフには常に入次数 0 のノードが存在するため、カーンのアルゴリズムは最終的にすべてのノードを削除し、有効な順序を返します。
すべてのノードを構築し、隣接する単語を走査するには O(C) かかります。異なるノードとエッジはそれぞれカーンのアルゴリズムによって1回処理されるため、合計時間は O(C + U + E)、追加空間は O(U + E) です。小文字 ASCII の場合、U は最大でも 26 ですが、記号による上限を維持することで推論を再利用可能にします。
複数の回答が可能な場合は、検証でプロパティを確認する必要があります。空でない結果には、入力の異なる文字がちょうど1回ずつ含まれていなければなりません。隣接するすべてのペアについて、返された順位マップを使用して比較し、ソートされていることを確認します。それとは別に、より長い単語がその接頭辞の前に来ていないことを確認します。1単語、重複単語、孤立文字、重複エッジの根拠、有効な接頭辞、無効な接頭辞、閉路、チェーン、および入次数 0 のノードが複数あるグラフをテストします。
白、灰、黒の状態を持つ DFS も正しい代替手段です。灰色のノードへのエッジを通じて閉路を検出し、結果としてポストオーダー（帰りがけ順）を反転します。カーンのアルゴリズムは ready セットを通じて曖昧性を可視化し、再帰の深さの懸念を回避できるため、この契約に対してより明確に推奨される方法です。
質の高い模範解答
「まず、ソートされた単語から半順序を推論する必要があります。エッジに関与しない文字も含め、すべての文字に対してノードを作成します。隣接するペアごとに、最初の不一致まで走査します。ペアが wrt と wrf の場合、t -> f を追加して終了します。それ以降の位置はその比較に影響を与えないためです。不一致がなく、最初の単語の方が長い場合（たとえば ab の前の abc など）、入力はすでに矛盾しています。
1つの関係に対する重複した根拠が入次数を1回だけ増やすように、隣接ノードをセットに格納します。次に、カーンのアルゴリズムを実行します。すべての入次数 0 の文字をエンキューし、1つを取り出して解答に追加し、その出力隣接ノードをデクリメントし、入次数が 0 になった隣接ノードをエンキューします。不変条件は、キューに入っている文字は未処理の文字の中に先行ノードが残っていないことであり、出力されるすべての文字が安全です。
出力の長さが重複のない文字数と等しい場合、推論されたすべてのエッジが尊重されています。それらのエッジと接頭辞チェックにより、隣接するすべての単語ペアが順序付けられるため、リスト全体が順序付けられます。長さが短い場合、残りのグラフには閉路が含まれており、どのアルファベットも成立しません。実行時間は O(C + U + E)、空間は O(U + E) です。接頭辞の前に長い単語があるケース、2エッジの閉路、1つのエッジに対する重複根拠、単一の単語、および複数の有効な出力があるケースをテストします。最後のケースでは、特定の1つの文字列を期待するのではなく、順序のプロパティを検証します。」
よくある間違い
- 単語ペア内の異なるすべての位置を使用する → 最初の不一致によって辞書順が決まった後は、それ以降の位置は関係しません → 最初の不一致のエッジのみを追加して停止してください。
- トポロジカルソートのみを実行する →
"ab"の前の"abc"はエッジを作成しないためすり抜けてしまいます → ペアの比較中に接頭辞の前に長い単語がある矛盾をチェックしてください。 - エッジを追加するときにのみノードを作成する → 孤立した文字が回答から消えてしまいます → 観察されたすべての文字に対してノードを初期化してください。
- 重複エッジに対して入次数を増やす → 有効なノードの入次数が 0 に達しなくなります → 隣接セットを使用し、最初の挿入時にのみ増やしてください。
- キューが空になったときに部分的な結果を返す → 巡回制約が成功したように見えてしまいます → 出力の長さが重複のない文字数と等しくなることを必須としてください。
- 1つの固定された答えを要求する → 有効な半順序には複数の線形拡張が存在する可能性があります → 返された順序を文字、エッジ、および単語の比較に対してテストしてください。
- すべての単語ペアを比較する → 処理が単語数の2乗になる可能性があります → ソート順を確立するには隣接比較で十分です。
- 曖昧性が無効な入力を意味すると主張する → 複数のアルファベットが同じ根拠を説明できます → 一意性が契約の一部でない限り、有効な順序をいずれか返してください。
フォローアップの質問と回答
フォローアップ1：アルファベットが一意であるかどうかをどのように判断しますか？
カーンのアルゴリズムの実行中、各取り出しの前に ready セットを検査します。2文字以上含まれることがあれば、少なくとも2つの選択肢を入れ替えて異なる有効なトポロジカル順序を作成できるため、根拠は曖昧です。常にちょうど1文字を含み、すべてのノードが処理された場合、順序は一意です。完了前に ready セットが空になった場合は、依然として閉路を意味します。
フォローアップ2：通常の文字順で最小の有効な結果を返すにはどうすればよいですか？
キューをホスト言語の文字順をキーとする最小ヒープに置き換えます。現在有効な最小の文字を選択することで、貪欲な交換論法により最小の線形拡張が生成されます。時間は O(C + E + U log U) になります。このタイブレークはエイリアンのアルファベットの外部にあることを明確に述べてください。
フォローアップ3：無効な入力に対して有用な説明を返すにはどうすればよいですか？
接頭辞の矛盾については、隣接する2つの単語とそのインデックスを返します。閉路については、カーン法が停止した後に残りのグラフで3色 DFS を実行し、親ポインタを保持して、後退エッジ（back-edge）の閉路を形成する文字を再構築します。構造化された結果により、空文字列を多重定義することなく invalid_prefix、cycle、および valid を区別できます。
フォローアップ4：単語リストをストリームとして処理できますか？
直前の単語を保持し、新しい単語ごとにノードを追加し、次の単語が到着したときに隣接ペアの制約を1つ導出します。後続の根拠によって先行ノードが追加されたり閉路が作成されたりする可能性があるため、ストリームが終了するまでグラフと入次数を保存しておく必要があります。ソースが終了境界を提供しない限り、すべての単語が観察された後にのみトポロジカルソートを実行します。
フォローアップ5：すべての有効なアルファベットを列挙するにはどうすればよいですか？
現在のすべての入次数 0 の文字に対してバックトラックを行います。1つを選択し、その出力エッジを削除し、再帰呼び出しを行い、その後状態を復元します。これにより有効な順序のみが列挙されますが、出力は U! に近づく可能性があります。実装する前に、小さなアルファベットであるか出力制限があるかを確認してください。
フォローアップ6：Unicode 単語の場合、何が変わりますか？
まず比較単位を定義します。コードポイントは常にユーザーが認識する文字と一致するとは限らず、ロケールの照合順序（collation）によって正規化形式や複数コードポイントのシーケンスが特別に扱われる場合があります。指定されたアルファベット記号に従って各単語をトークン化し、契約で要求されている場合のみ正規化し、トークンに対して同じグラフアルゴリズムを実行します。その契約がなければ、「文字順」は未定義となります。