[Leetcode] 0269. Alien Dictionary

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

內容目錄

Hard

There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you.

You are given a list of strings words from the alien language’s dictionary. Now it is claimed that the strings in words are sorted lexicographically by the rules of this new language.

If this claim is incorrect, and the given arrangement of string in words cannot correspond to any order of letters, return "".

Otherwise, return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language’s rules. If there are multiple solutions, return any of them.

Example 1:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

Example 2:

Input: words = ["z","x"]
Output: "zx"

Example 3:

Input: words = ["z","x","z"]
Output: ""
Explanation: The order is invalid, so return "".

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of only lowercase English letters.

Python

				
					# time complexity: O(C)
# space complexity: O(1)
from typing import List


class Solution:
    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 node in 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))

Hard

Python

相關文章