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:
-
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
""
. -
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:
- We build a directed graph from character relationships by comparing adjacent words
- We detect if there are any cycles (invalid ordering)
- 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.
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 EvaluatorExample 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:
-
"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)
- Mark characters in "wrt": w, r, t as seen (
-
"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
- Mark characters in "wrf": w, r, f as seen (f is new,
-
"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
- Mark characters in "er": e, r as seen (e is new,
-
"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 takesO(min(len(words[i]), len(words[i+1])))
time. In the worst case, this isO(C)
whereC
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)
whereV β€ 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.
Which of the following array represent a max heap?
Recommended Readings
https assets algo monster cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS As the name suggests
https assets algo monster cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell Breadth First Search BFS
https assets algo monster cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could be disconnected A tree
Want a Structured Path to Master System Design Too? Donβt Miss This!