We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Alien Dictionary

Number: 269

Difficulty: Hard

Paid? Yes

Companies: Meta, Uber, Google, Amazon, TikTok, Microsoft, Oracle, Airbnb, Flipkart, PhonePe, Citadel, X, Snap, Pocket Gems, Wix

Problem Description

Given a list of words from an alien dictionary, determine the order of characters in the alien language. The words are sorted lexicographically, but the character order is unknown. Compute a valid character order that respects the provided lexicographical order. If no valid order exists, return an empty string.

Key Insights

  • Build a graph where each unique character is a node.
  • Compare adjacent words to determine the first different character, which gives the ordering (directed edge).
  • Ensure all characters, even those without edges, are represented.
  • Use a topological sort (using DFS or BFS) to determine a valid character ordering.
  • Handle edge cases, such as words where a longer word appears before its prefix which is invalid.

Space and Time Complexity

Time Complexity: O(N * L + V + E) where N is the number of words, L is the average length of each word, V is the number of unique characters, and E is the number of edges derived from adjacent word comparisons. Space Complexity: O(V + E) for storing the graph and additional data structures for topological sorting.

Solution

We use a graph-based approach to solve the problem. First, we initialize a graph (adjacency list) and in-degree dictionary for all unique characters. We then iterate through each pair of consecutive words, comparing them character by character to find the first pair that differs. This difference implies an order: the first character should come before the second character. We add a directed edge accordingly and update the in-degree for the target character.

To get the final ordering, we perform a topological sort using Kahn’s algorithm:

  1. Enqueue characters with in-degree zero.
  2. Remove characters from the queue and append them to our result.
  3. Decrement the in-degree of neighboring nodes.
  4. If a neighbor's in-degree becomes zero, enqueue it. If the result’s length equals the number of unique nodes, we have a valid ordering; otherwise, a cycle exists, and we return an empty string.

Code Solutions

# Python solution for Alien Dictionary
from collections import defaultdict, deque

def alienOrder(words):
    # Create data structures: graph and in_degree for each unique character.
    graph = defaultdict(set)
    in_degree = {char: 0 for word in words for char in word}
    
    # Build the graph.
    for i in range(len(words) - 1):
        word1, word2 = words[i], words[i+1]
        # Check for invalid case where prefix of next word is the same but word1 is longer.
        if len(word1) > len(word2) and word1.startswith(word2):
            return ""
        # Compare the words character by character.
        for c1, c2 in zip(word1, word2):
            if c1 != c2:
                # If we haven't already recorded this edge, add it.
                if c2 not in graph[c1]:
                    graph[c1].add(c2)
                    in_degree[c2] += 1
                break

    # Prepare for topological sort by adding all nodes with in_degree == 0.
    queue = deque([char for char in in_degree if in_degree[char] == 0])
    order = []
    
    # Kahn's algorithm for topological sort.
    while queue:
        current = queue.popleft()
        order.append(current)
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Check if topological sort is possible.
    if len(order) == len(in_degree):
        return "".join(order)
    else:
        return ""
        
# Example usage:
print(alienOrder(["wrt","wrf","er","ett","rftt"]))
← Back to All Questions