[リートコード] 0269. エイリアン辞典

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

難しい

英語のアルファベットを使用する新しいエイリアンの言語がありますが、その文字の順序はわかりません。

文字列のリストが与えられます 言葉 エイリアン言語の辞書からは、次の文字列が得られると主張されています。 言葉 は 辞書順にソート この新しい言語のルールに従って。

この主張が正しくなく、指定された文字列の配置が間違っている場合、 言葉 いかなる文字順でも対応できません、返品 "".

それ以外の場合は戻ります 新しいエイリアン言語の一意の文字列を並べ替えたもの 辞書順の昇順 新しい言語のルールに従って. 複数の解がある場合は戻ります それらのどれか.

例 1:

入力： 単語 = ["wrt","wrf","er","ett","rftt"]
出力： 「ヴェルトフ」

例 2:

入力： 単語 = ["z","x"]
出力： 「ゼクス」

例 3:

入力： 単語 = ["z","x","z"]
出力： ""
説明： 注文は無効ですので返品してください "".

制約:

1 <= 単語.長さ <= 100
1 <= 単語[i].length <= 100
言葉[i] 小文字の英字のみで構成されています。

パイソン

				
					# 時間計算量: O(C) # 空間計算量: import リスト クラスの入力による O(1) 解決策: def AlienOrder(self, Words: List[str]) -> str: reverseAdjList = {c: [] for word in Words for c in word} for firstWord, SecondWord in zip(words, Words[1:]): for c, d in zip(firstWord, SecondWord): if c != d: reverseAdjList[d].append(c) Break else : if len(secondWord) < len(firstWord): return "" seen = {} Output = [] def visit(node): if ノードが seen: return seen[node] seen[node] = False for nextNode in reverseAdjList[ node]: result = visit(nextNode) if not result: return False seen[node] = True Output.append(node) return True if not all(visit(node) for node in reverseAdjList): return "" return ""。 join(output)words = ["wrt", "wrf", "er", "ett", "rftt"] print(Solution().alienOrder(words))

難しい

パイソン

関連記事