29 / 75
Hard
Alien Dictionary
#29graphtopological-sortdfsbfsstring
Build graph from word order relationships and return topological sort of character ordering.
Example:
Input:
words=['wrt','wrf','er','ett','rftt']Output:
'wertf' (one possible valid ordering)Common Mistakes:
- Not handling invalid cases (w1='abc', w2='ab' where w1 > w2)
- Comparing all character pairs instead of just first difference
- Forgetting to include all characters in graph (even those with no edges)
- Not detecting cycles (return empty string)
Notes:
This is a LeetCode Premium problem. Time O(C) where C is total chars in all words. Space O(1) for graph (max 26 letters).
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Build graph from word order relationships and return topological sort of character ordering.
Example:
Input:
words=['wrt','wrf','er','ett','rftt']Output:
'wertf' (one possible valid ordering)Common Mistakes:
- Not handling invalid cases (w1='abc', w2='ab' where w1 > w2)
- Comparing all character pairs instead of just first difference
- Forgetting to include all characters in graph (even those with no edges)
- Not detecting cycles (return empty string)
Notes:
This is a LeetCode Premium problem. Time O(C) where C is total chars in all words. Space O(1) for graph (max 26 letters).
29/75
Alien Dictionary