Facebook Pixel

269. Alien Dictionary πŸ”’

Problem Description

You're given a list of words from an alien language that uses the same 26 letters as English, but the alphabetical order of these letters is different and unknown to you.

The words are claimed to be sorted in dictionary order according to this alien alphabet. Your task is to:

  1. Verify if the claim is valid: Check if the given word order can actually correspond to some valid alphabetical ordering of letters. If not, return an empty string "".

  2. Recover the alien alphabet: If the ordering is valid, determine what the alphabetical order of letters must be in this alien language and return it as a string containing all unique letters that appear in the words, sorted according to the alien alphabet's rules.

Key Points:

  • The words should follow lexicographic ordering based on the alien alphabet (like how words are ordered in a dictionary)
  • You need to deduce the relative order of letters by comparing adjacent words in the list
  • If there are multiple valid orderings possible, return any one of them
  • If the given arrangement is impossible (contradicts itself), return ""

Example of Invalid Input: If you have words like ["abc", "ab"], this would be invalid because in any alphabet, "abc" cannot come before "ab" in dictionary order (a longer word with the same prefix must come after the shorter word).

Example of Deducing Order: If you have words ["wrt", "wrf"], you can deduce that 't' comes before 'f' in the alien alphabet since these words differ at the third position and "wrt" comes before "wrf".

The solution uses topological sorting to build the alphabet order from the character relationships derived from comparing adjacent words.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • Yes: The problem involves relationships between characters that can be modeled as a graph. Each character is a node, and the ordering relationships between characters form directed edges.

Is it a tree?

  • No: The relationship structure is not a tree. Characters can have multiple predecessors and successors, forming a more general directed graph structure.

Is the problem related to directed acyclic graphs?

  • Yes: The character ordering relationships form a directed graph that must be acyclic (DAG). If there's a cycle in the ordering (e.g., 'a' < 'b' < 'c' < 'a'), then no valid alphabet ordering exists, and we return "".

Topological Sort

  • Yes: This is the algorithm we need! Topological sort is perfect for finding a linear ordering of nodes in a DAG, which is exactly what we need - a linear ordering of characters that respects all the precedence relationships we've discovered.

Conclusion: The flowchart leads us to use Topological Sort, which can be implemented using DFS. In the solution:

  1. We build a directed graph from character relationships by comparing adjacent words
  2. We detect if there are any cycles (invalid ordering)
  3. We perform topological sort using DFS (or BFS with indegree counting as shown in the solution) to get the final character ordering

The DFS pattern appears in the topological sort implementation, where we traverse the graph to determine the valid ordering of characters while checking for cycles that would indicate an impossible arrangement.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is recognizing that determining the alien alphabet order is fundamentally about finding dependencies between characters. When we compare two adjacent words in the sorted list, we can extract one piece of information about the relative ordering of two characters.

Think about how dictionary ordering works: when comparing "apple" and "application", we look at characters from left to right. The first difference tells us the ordering - since "apple" comes before "application" and they differ at position 5 ('e' vs 'i'), we know 'e' comes before 'i' in the alphabet.

Similarly, for the alien dictionary, when we see ["wrt", "wrf"], we compare character by character:

  • 'w' = 'w' (same, continue)
  • 'r' = 'r' (same, continue)
  • 't' β‰  'f' (different!)

Since "wrt" comes before "wrf" in the sorted list, we deduce that 't' must come before 'f' in the alien alphabet.

Each such comparison gives us a directed edge in a graph: 't' β†’ 'f' means 't' comes before 'f'. After processing all adjacent word pairs, we have a directed graph representing all the ordering constraints.

Now the problem transforms into: "Given all these ordering constraints (directed edges), can we find a valid total ordering of all characters?" This is exactly what topological sorting does - it finds a linear ordering of nodes in a directed graph such that for every edge u β†’ v, u comes before v in the ordering.

The catch is that topological sorting only works on Directed Acyclic Graphs (DAGs). If there's a cycle (like 'a' β†’ 'b' β†’ 'c' β†’ 'a'), then no valid ordering exists. Also, if we find a contradiction like a longer word appearing before its prefix (e.g., "abc" before "ab"), we know the input is invalid.

The solution naturally follows: build the graph from word comparisons, check for invalid cases, and perform topological sort to get the character ordering.

Solution Approach

The implementation follows these key steps:

1. Build the Graph and Track Characters

First, we create a directed graph using a 2D boolean array g[26][26] where g[i][j] = True means character i comes before character j. We also track which characters appear in the words using array s[26] and count them with cnt.

g = [[False] * 26 for _ in range(26)]  # Adjacency matrix for graph
s = [False] * 26  # Track which characters exist
cnt = 0  # Count of unique characters

2. Extract Ordering Relationships

For each pair of adjacent words, we compare them character by character to find the first difference:

for i in range(n - 1):
    # First, mark all characters in current word as seen
    for c in words[i]:
        o = ord(c) - ord('a')
        if not s[o]:
            cnt += 1
            s[o] = True
  
    # Compare with next word
    for j in range(len(words[i])):
        if j >= len(words[i + 1]):
            return ''  # Invalid: longer word before its prefix
      
        c1, c2 = words[i][j], words[i + 1][j]
        if c1 == c2:
            continue  # Same character, keep comparing
      
        # Found first difference
        o1, o2 = ord(c1) - ord('a'), ord(c2) - ord('a')
        if g[o2][o1]:
            return ''  # Contradiction: reverse edge already exists
        g[o1][o2] = True  # Add edge: c1 comes before c2
        break

3. Topological Sort using Kahn's Algorithm

We use BFS-based topological sort (Kahn's algorithm) with indegree counting:

# Calculate indegrees for all characters
indegree = [0] * 26
for i in range(26):
    for j in range(26):
        if i != j and s[i] and s[j] and g[i][j]:
            indegree[j] += 1

# Start with characters having no dependencies (indegree = 0)
q = deque()
for i in range(26):
    if s[i] and indegree[i] == 0:
        q.append(i)

# Process characters in topological order
ans = []
while q:
    t = q.popleft()
    ans.append(chr(t + ord('a')))
  
    # Remove this character's edges and update indegrees
    for i in range(26):
        if s[i] and i != t and g[t][i]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

4. Validate Result

Finally, we check if we processed all characters. If len(ans) < cnt, it means there's a cycle in the graph (some characters never reached indegree 0), so we return empty string:

return '' if len(ans) < cnt else ''.join(ans)

The algorithm efficiently handles:

  • Invalid prefix cases: When a word is a prefix of an earlier word
  • Contradictions: When we find conflicting ordering requirements
  • Cycles: When the ordering constraints form a cycle
  • Multiple valid solutions: Returns any valid topological ordering

Time complexity: O(C) where C is the total number of characters in all words, as we process each character at most once when comparing words and the graph operations are bounded by the alphabet size (26).

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example with the words: ["wrt", "wrf", "er", "ett", "rftt"]

Step 1: Initialize Data Structures

  • Create a 26Γ—26 graph matrix g (all False initially)
  • Create array s to track which letters appear (all False initially)
  • Set cnt = 0 to count unique characters

Step 2: Extract Ordering Relationships

Compare adjacent words to find character dependencies:

  1. "wrt" vs "wrf":

    • Mark characters in "wrt": w, r, t as seen (cnt = 3)
    • Compare: w=w (same), r=r (same), tβ‰ f (different!)
    • Add edge: t β†’ f (meaning t comes before f)
  2. "wrf" vs "er":

    • Mark characters in "wrf": w, r, f as seen (f is new, cnt = 4)
    • Compare: wβ‰ e (different!)
    • Add edge: w β†’ e
  3. "er" vs "ett":

    • Mark characters in "er": e, r as seen (e is new, cnt = 5)
    • Compare: e=e (same), rβ‰ t (different!)
    • Add edge: r β†’ t
  4. "ett" vs "rftt":

    • Mark characters in "ett": e, t as seen (all already seen)
    • Compare: eβ‰ r (different!)
    • Add edge: e β†’ r

After processing the last word "rftt", all characters are marked (cnt = 5 total: w, r, t, f, e)

Our graph now has edges:

  • t β†’ f
  • w β†’ e
  • r β†’ t
  • e β†’ r

Step 3: Calculate Indegrees Count incoming edges for each character:

  • w: 0 (no incoming edges)
  • e: 1 (from w)
  • r: 1 (from e)
  • t: 1 (from r)
  • f: 1 (from t)

Step 4: Topological Sort

Start with characters having indegree 0:

  • Queue: [w]
  • Result: []

Process w:

  • Add 'w' to result: ['w']
  • Remove edge w β†’ e, reducing e's indegree to 0
  • Queue: [e]

Process e:

  • Add 'e' to result: ['w', 'e']
  • Remove edge e β†’ r, reducing r's indegree to 0
  • Queue: [r]

Process r:

  • Add 'r' to result: ['w', 'e', 'r']
  • Remove edge r β†’ t, reducing t's indegree to 0
  • Queue: [t]

Process t:

  • Add 't' to result: ['w', 'e', 'r', 't']
  • Remove edge t β†’ f, reducing f's indegree to 0
  • Queue: [f]

Process f:

  • Add 'f' to result: ['w', 'e', 'r', 't', 'f']
  • Queue: [] (empty)

Step 5: Validate and Return

  • We processed 5 characters and cnt = 5, so all characters were included
  • No cycles detected
  • Return: "wertf"

This represents the alien alphabet order where w < e < r < t < f. You can verify this ordering makes the original word list correctly sorted!

Solution Implementation

1class Solution:
2    def alienOrder(self, words: List[str]) -> str:
3        # Initialize adjacency matrix for the directed graph
4        # graph[i][j] = True means character i comes before character j
5        graph = [[False] * 26 for _ in range(26)]
6      
7        # Track which characters appear in the words
8        seen_chars = [False] * 26
9        char_count = 0
10        num_words = len(words)
11      
12        # Build the graph by comparing adjacent words
13        for i in range(num_words - 1):
14            # Mark all characters in current word as seen
15            for char in words[i]:
16                if char_count == 26:
17                    break
18                char_index = ord(char) - ord('a')
19                if not seen_chars[char_index]:
20                    char_count += 1
21                    seen_chars[char_index] = True
22          
23            # Compare current word with next word to find ordering
24            curr_word_len = len(words[i])
25            for j in range(curr_word_len):
26                # If current word is longer than next word and they match up to this point,
27                # the ordering is invalid (e.g., "abc" cannot come before "ab")
28                if j >= len(words[i + 1]):
29                    return ''
30              
31                char1, char2 = words[i][j], words[i + 1][j]
32                if char1 == char2:
33                    continue
34              
35                # Found first different character - this gives us ordering information
36                index1, index2 = ord(char1) - ord('a'), ord(char2) - ord('a')
37              
38                # Check for contradictory ordering (char2 already comes before char1)
39                if graph[index2][index1]:
40                    return ''
41              
42                # Add edge: char1 comes before char2
43                graph[index1][index2] = True
44                break
45      
46        # Mark characters in the last word as seen
47        for char in words[num_words - 1]:
48            if char_count == 26:
49                break
50            char_index = ord(char) - ord('a')
51            if not seen_chars[char_index]:
52                char_count += 1
53                seen_chars[char_index] = True
54      
55        # Calculate in-degrees for topological sort
56        in_degree = [0] * 26
57        for i in range(26):
58            for j in range(26):
59                if i != j and seen_chars[i] and seen_chars[j] and graph[i][j]:
60                    in_degree[j] += 1
61      
62        # Perform topological sort using Kahn's algorithm
63        queue = deque()
64        result = []
65      
66        # Add all characters with in-degree 0 to queue
67        for i in range(26):
68            if seen_chars[i] and in_degree[i] == 0:
69                queue.append(i)
70      
71        # Process queue
72        while queue:
73            curr_char_index = queue.popleft()
74            result.append(chr(curr_char_index + ord('a')))
75          
76            # Reduce in-degree for all neighbors
77            for i in range(26):
78                if seen_chars[i] and i != curr_char_index and graph[curr_char_index][i]:
79                    in_degree[i] -= 1
80                    if in_degree[i] == 0:
81                        queue.append(i)
82      
83        # If we couldn't process all characters, there's a cycle
84        return '' if len(result) < char_count else ''.join(result)
85
1class Solution {
2  
3    public String alienOrder(String[] words) {
4        // Graph representation: graph[i][j] = true means character i comes before character j
5        boolean[][] graph = new boolean[26][26];
6        // Track which characters appear in the input
7        boolean[] seen = new boolean[26];
8        // Count of unique characters
9        int uniqueCharCount = 0;
10        int numWords = words.length;
11      
12        // Process each adjacent pair of words to build the graph
13        for (int i = 0; i < numWords - 1; i++) {
14            // Mark all characters in current word as seen
15            for (char c : words[i].toCharArray()) {
16                if (uniqueCharCount == 26) {
17                    break;
18                }
19                int charIndex = c - 'a';
20                if (!seen[charIndex]) {
21                    uniqueCharCount++;
22                    seen[charIndex] = true;
23                }
24            }
25          
26            // Compare current word with next word to find ordering
27            int currentWordLength = words[i].length();
28            for (int j = 0; j < currentWordLength; j++) {
29                // If next word is shorter but matches so far, invalid ordering
30                // Example: ["abc", "ab"] is invalid
31                if (j >= words[i + 1].length()) {
32                    return "";
33                }
34              
35                char char1 = words[i].charAt(j);
36                char char2 = words[i + 1].charAt(j);
37              
38                // Skip if characters are the same
39                if (char1 == char2) {
40                    continue;
41                }
42              
43                // Check for cycle: if char2 -> char1 already exists, adding char1 -> char2 creates a cycle
44                if (graph[char2 - 'a'][char1 - 'a']) {
45                    return "";
46                }
47              
48                // Add edge: char1 comes before char2
49                graph[char1 - 'a'][char2 - 'a'] = true;
50                break; // Only the first different character determines the order
51            }
52        }
53      
54        // Mark all characters in the last word as seen
55        for (char c : words[numWords - 1].toCharArray()) {
56            if (uniqueCharCount == 26) {
57                break;
58            }
59            int charIndex = c - 'a';
60            if (!seen[charIndex]) {
61                uniqueCharCount++;
62                seen[charIndex] = true;
63            }
64        }
65      
66        // Calculate indegree for each character (topological sort preparation)
67        int[] indegree = new int[26];
68        for (int from = 0; from < 26; from++) {
69            for (int to = 0; to < 26; to++) {
70                if (from != to && seen[from] && seen[to] && graph[from][to]) {
71                    indegree[to]++;
72                }
73            }
74        }
75      
76        // Initialize queue with all characters that have indegree 0
77        Deque<Integer> queue = new LinkedList<>();
78        for (int i = 0; i < 26; i++) {
79            if (seen[i] && indegree[i] == 0) {
80                queue.offerLast(i);
81            }
82        }
83      
84        // Perform topological sort using BFS (Kahn's algorithm)
85        StringBuilder result = new StringBuilder();
86        while (!queue.isEmpty()) {
87            int current = queue.pollFirst();
88            result.append((char) (current + 'a'));
89          
90            // Reduce indegree for all neighbors
91            for (int neighbor = 0; neighbor < 26; neighbor++) {
92                if (neighbor != current && seen[neighbor] && graph[current][neighbor]) {
93                    indegree[neighbor]--;
94                    if (indegree[neighbor] == 0) {
95                        queue.offerLast(neighbor);
96                    }
97                }
98            }
99        }
100      
101        // If we couldn't process all characters, there's a cycle
102        return result.length() < uniqueCharCount ? "" : result.toString();
103    }
104}
105
1class Solution {
2public:
3    string alienOrder(vector<string>& words) {
4        // Graph adjacency matrix: graph[i][j] = true means character i comes before character j
5        vector<vector<bool>> graph(26, vector<bool>(26, false));
6      
7        // Track which characters appear in the words
8        vector<bool> seen(26, false);
9        int uniqueCharCount = 0;
10      
11        int numWords = words.size();
12      
13        // Process adjacent word pairs to build the graph
14        for (int i = 0; i < numWords - 1; ++i) {
15            // Mark all characters in current word as seen
16            for (char ch : words[i]) {
17                if (uniqueCharCount == 26) break;
18                int charIndex = ch - 'a';
19                if (!seen[charIndex]) {
20                    ++uniqueCharCount;
21                    seen[charIndex] = true;
22                }
23            }
24          
25            // Compare current word with next word to find ordering relationship
26            int currentWordLen = words[i].size();
27            for (int j = 0; j < currentWordLen; ++j) {
28                // If next word is prefix of current word, invalid ordering
29                if (j >= words[i + 1].size()) {
30                    return "";
31                }
32              
33                char char1 = words[i][j];
34                char char2 = words[i + 1][j];
35              
36                // Skip if characters are the same
37                if (char1 == char2) continue;
38              
39                // Check for contradiction: if char2 -> char1 already exists
40                if (graph[char2 - 'a'][char1 - 'a']) {
41                    return "";
42                }
43              
44                // Add edge: char1 -> char2
45                graph[char1 - 'a'][char2 - 'a'] = true;
46                break;  // Only first differing character matters
47            }
48        }
49      
50        // Mark characters in the last word as seen
51        for (char ch : words[numWords - 1]) {
52            if (uniqueCharCount == 26) break;
53            int charIndex = ch - 'a';
54            if (!seen[charIndex]) {
55                ++uniqueCharCount;
56                seen[charIndex] = true;
57            }
58        }
59      
60        // Calculate indegree for each character
61        vector<int> indegree(26, 0);
62        for (int from = 0; from < 26; ++from) {
63            for (int to = 0; to < 26; ++to) {
64                if (from != to && seen[from] && seen[to] && graph[from][to]) {
65                    ++indegree[to];
66                }
67            }
68        }
69      
70        // Initialize queue with all characters having indegree 0
71        queue<int> zeroIndegreeQueue;
72        for (int i = 0; i < 26; ++i) {
73            if (seen[i] && indegree[i] == 0) {
74                zeroIndegreeQueue.push(i);
75            }
76        }
77      
78        // Perform topological sort using Kahn's algorithm
79        string result = "";
80        while (!zeroIndegreeQueue.empty()) {
81            int currentChar = zeroIndegreeQueue.front();
82            zeroIndegreeQueue.pop();
83            result += (currentChar + 'a');
84          
85            // Decrease indegree of all neighbors
86            for (int neighbor = 0; neighbor < 26; ++neighbor) {
87                if (neighbor != currentChar && seen[neighbor] && graph[currentChar][neighbor]) {
88                    if (--indegree[neighbor] == 0) {
89                        zeroIndegreeQueue.push(neighbor);
90                    }
91                }
92            }
93        }
94      
95        // If result doesn't contain all unique characters, there's a cycle
96        return result.size() < uniqueCharCount ? "" : result;
97    }
98};
99
1function alienOrder(words: string[]): string {
2    // Graph adjacency matrix: graph[i][j] = true means character i comes before character j
3    const graph: boolean[][] = Array(26).fill(null).map(() => Array(26).fill(false));
4  
5    // Track which characters appear in the words
6    const seen: boolean[] = Array(26).fill(false);
7    let uniqueCharCount = 0;
8  
9    const numWords = words.length;
10  
11    // Process adjacent word pairs to build the graph
12    for (let i = 0; i < numWords - 1; i++) {
13        // Mark all characters in current word as seen
14        for (const ch of words[i]) {
15            if (uniqueCharCount === 26) break;
16            const charIndex = ch.charCodeAt(0) - 'a'.charCodeAt(0);
17            if (!seen[charIndex]) {
18                uniqueCharCount++;
19                seen[charIndex] = true;
20            }
21        }
22      
23        // Compare current word with next word to find ordering relationship
24        const currentWordLen = words[i].length;
25        for (let j = 0; j < currentWordLen; j++) {
26            // If next word is prefix of current word, invalid ordering
27            if (j >= words[i + 1].length) {
28                return "";
29            }
30          
31            const char1 = words[i][j];
32            const char2 = words[i + 1][j];
33          
34            // Skip if characters are the same
35            if (char1 === char2) continue;
36          
37            // Check for contradiction: if char2 -> char1 already exists
38            if (graph[char2.charCodeAt(0) - 'a'.charCodeAt(0)][char1.charCodeAt(0) - 'a'.charCodeAt(0)]) {
39                return "";
40            }
41          
42            // Add edge: char1 -> char2
43            graph[char1.charCodeAt(0) - 'a'.charCodeAt(0)][char2.charCodeAt(0) - 'a'.charCodeAt(0)] = true;
44            break;  // Only first differing character matters
45        }
46    }
47  
48    // Mark characters in the last word as seen
49    for (const ch of words[numWords - 1]) {
50        if (uniqueCharCount === 26) break;
51        const charIndex = ch.charCodeAt(0) - 'a'.charCodeAt(0);
52        if (!seen[charIndex]) {
53            uniqueCharCount++;
54            seen[charIndex] = true;
55        }
56    }
57  
58    // Calculate indegree for each character
59    const indegree: number[] = Array(26).fill(0);
60    for (let from = 0; from < 26; from++) {
61        for (let to = 0; to < 26; to++) {
62            if (from !== to && seen[from] && seen[to] && graph[from][to]) {
63                indegree[to]++;
64            }
65        }
66    }
67  
68    // Initialize queue with all characters having indegree 0
69    const zeroIndegreeQueue: number[] = [];
70    for (let i = 0; i < 26; i++) {
71        if (seen[i] && indegree[i] === 0) {
72            zeroIndegreeQueue.push(i);
73        }
74    }
75  
76    // Perform topological sort using Kahn's algorithm
77    let result = "";
78    while (zeroIndegreeQueue.length > 0) {
79        const currentChar = zeroIndegreeQueue.shift()!;
80        result += String.fromCharCode(currentChar + 'a'.charCodeAt(0));
81      
82        // Decrease indegree of all neighbors
83        for (let neighbor = 0; neighbor < 26; neighbor++) {
84            if (neighbor !== currentChar && seen[neighbor] && graph[currentChar][neighbor]) {
85                indegree[neighbor]--;
86                if (indegree[neighbor] === 0) {
87                    zeroIndegreeQueue.push(neighbor);
88                }
89            }
90        }
91    }
92  
93    // If result doesn't contain all unique characters, there's a cycle
94    return result.length < uniqueCharCount ? "" : result;
95}
96

Time and Space Complexity

Time Complexity: O(V + E) where V is the number of unique characters and E is the number of edges in the graph, or more precisely O(C) where C is the total number of characters in all words.

  • Building the graph: We iterate through n-1 pairs of adjacent words. For each pair, we compare characters up to the length of the shorter word, which takes O(min(len(words[i]), len(words[i+1]))) time. In the worst case, this is O(C) where C is the total number of characters.
  • Counting unique characters: We iterate through all characters in all words once, which is O(C).
  • Building the indegree array: We check all possible edges in the graph, which is O(26 * 26) = O(1) since the alphabet size is fixed at 26.
  • Topological sort using BFS: We process each unique character once and for each character, we check all 26 possible outgoing edges. This is O(V * 26) = O(V) where V ≀ 26.

Overall time complexity: O(C + V^2) where V ≀ 26, which simplifies to O(C) since V is bounded by a constant.

Space Complexity: O(1) or O(V^2) where V ≀ 26

  • Graph adjacency matrix g: O(26 * 26) = O(1)
  • Character existence array s: O(26) = O(1)
  • Indegree array: O(26) = O(1)
  • Queue for BFS: O(26) = O(1) in the worst case
  • Answer list: O(26) = O(1) in the worst case

Since the alphabet size is fixed at 26, all space used is constant, giving us O(1) space complexity.

Common Pitfalls

1. Missing the Prefix Validation Check

One of the most common pitfalls is forgetting to check if a word is a prefix of its predecessor. When comparing adjacent words, if we exhaust all characters of the current word without finding a difference, but the next word is shorter, this represents an invalid ordering.

Incorrect approach:

# Many solutions forget this critical check
for j in range(min(len(words[i]), len(words[i + 1]))):
    if words[i][j] != words[i + 1][j]:
        # Add edge and break
        break
# Missing: what if all characters match but words[i] is longer?

Correct approach:

for j in range(len(words[i])):
    # Check if next word is shorter (invalid case)
    if j >= len(words[i + 1]):
        return ''  # "abc" cannot come before "ab"
  
    if words[i][j] != words[i + 1][j]:
        # Add edge and break
        break

2. Not Detecting All Characters in the Words

Another pitfall is only tracking characters that appear in the ordering relationships (edges), missing characters that appear in words but don't have any ordering constraints.

Incorrect approach:

# Only tracking characters when adding edges
if char1 != char2:
    seen_chars[ord(char1) - ord('a')] = True
    seen_chars[ord(char2) - ord('a')] = True
    # Missing: characters that never differ between adjacent words

Correct approach:

# Track ALL characters that appear in ANY word
for i in range(num_words):
    for char in words[i]:
        char_index = ord(char) - ord('a')
        if not seen_chars[char_index]:
            char_count += 1
            seen_chars[char_index] = True

3. Incorrectly Handling Isolated Characters

Characters that appear in the words but have no ordering relationships (no incoming or outgoing edges) still need to be included in the final result. These characters have in-degree 0 and should be added to the initial queue.

Incorrect approach:

# Only considering characters that have edges
for i in range(26):
    if graph[i].any() or any(graph[j][i] for j in range(26)):
        if in_degree[i] == 0:
            queue.append(i)

Correct approach:

# Include ALL seen characters with in-degree 0
for i in range(26):
    if seen_chars[i] and in_degree[i] == 0:
        queue.append(i)

4. Not Checking for Contradictory Edges

When adding a new edge to the graph, it's important to check if the reverse edge already exists, which would indicate a contradiction in the ordering.

Incorrect approach:

# Blindly adding edges without checking for contradictions
if char1 != char2:
    graph[index1][index2] = True
    break

Correct approach:

if char1 != char2:
    index1, index2 = ord(char1) - ord('a'), ord(char2) - ord('a')
    # Check if reverse edge exists (contradiction)
    if graph[index2][index1]:
        return ''
    graph[index1][index2] = True
    break

5. Breaking Too Early When Building the Graph

A subtle pitfall is breaking out of the comparison loop even when characters are equal, or not breaking when a difference is found.

Incorrect approach:

for j in range(min(len(words[i]), len(words[i + 1]))):
    char1, char2 = words[i][j], words[i + 1][j]
    # Wrong: might break even when chars are equal
    # or might continue after finding first difference
    if char1 != char2:
        graph[ord(char1) - ord('a')][ord(char2) - ord('a')] = True
    # Missing break statement

Correct approach:

for j in range(len(words[i])):
    if j >= len(words[i + 1]):
        return ''
  
    char1, char2 = words[i][j], words[i + 1][j]
    if char1 == char2:
        continue  # Keep comparing if characters are equal
  
    # Process the first difference and break immediately
    index1, index2 = ord(char1) - ord('a'), ord(char2) - ord('a')
    if graph[index2][index1]:
        return ''
    graph[index1][index2] = True
    break  # Must break after finding first difference

These pitfalls can lead to incorrect results, missing characters in the output, or failure to detect invalid inputs. The solution provided handles all these cases correctly by carefully validating inputs, tracking all characters, and properly implementing the topological sort.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Which of the following array represent a max heap?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More