Alien Dictionary

Clarify the problem

• The problem asks us to determine the order of characters in an alien language given a list of words.
• The input will be an array of words, and the output should be a string representing the order of characters.
• We need to handle the case where the given input is invalid or does not have a valid order.

Analyze the problem

• We can think of this problem as a graph problem, where the characters are nodes, and the relationships between characters can be represented as directed edges.
• The order of characters can be found by performing a topological sort on the graph.
• We need to construct the graph by comparing adjacent words and finding the first differing characters.
• The constraints are not explicitly given, but we can assume that the words are non-empty and consist only of lowercase letters.

Design an algorithm

• Initialize an empty graph to store the relationships between characters.
• Construct the graph by comparing adjacent words and finding the first differing characters.
• Perform a topological sort on the graph to find the order of characters.
• Handle cases where the graph is cyclic or there is no valid order.

Explain your approach

• I will start by initializing an empty graph using a dictionary to represent the relationships between characters.
• I will then compare adjacent words and find the first differing characters to construct the graph.
• After constructing the graph, I will perform a topological sort to find the order of characters.
• If the graph is cyclic or there is no valid order, I will return an empty string.

Write clean and readable code

def alienOrder(words):
    graph = {}  # Dictionary to store relationships between characters

    # Construct the graph
    for i in range(len(words) - 1):
        for j in range(min(len(words[i]), len(words[i+1]))):
            if words[i][j] != words[i+1][j]:
                if words[i][j] not in graph:
                    graph[words[i][j]] = set()
                graph[words[i][j]].add(words[i+1][j])
                break

    # Perform topological sort
    visited = {}
    result = []

    def dfs(node):
        if node in visited:
            if visited[node] == 0:
                return False
            else:
                return True
        visited[node] = 0
        if node in graph:
            for neighbor in graph[node]:
                if not dfs(neighbor):
                    return False
        visited[node] = 1
        result.append(node)
        return True

    for node in graph:
        if not dfs(node):
            return ""

    return ''.join(result[::-1])  # Reverse the result to get the correct order

Test your code

print(alienOrder(["wrt", "wrf", "er", "ett", "rftt"]))
# Output: "wertf"