Verifying an Alien Dictionary - Solution & Explanation
Problem Statement
In an alien language, surprisingly, they also use English lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.
Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographically in this alien language.
Example 1:
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz" Output: true Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.
Example 2:
Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz" Output: false Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.
Example 3:
Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz" Output: false Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 20order.length == 26- All characters in
words[i]andorderare English lowercase letters.
Approach Overview
Problem Overview: You receive a list of words and a string describing the alphabet order used by an alien language. Your job is to verify whether the words are sorted according to that custom character order.
The challenge is that the alphabetical order is not the normal English order. You must interpret comparisons between characters using the alien alphabet mapping and check every adjacent pair of words.
Approach 1: Mapping Order Using Indexes (O(n * m) time, O(1) space)
Create a lookup table that maps each character in the alien alphabet to its index (rank). This can be stored in a small array or hash map where order[i] tells you the priority of the character. Then iterate through each adjacent pair of words and compare them character by character. As soon as you find different characters, check their mapped ranks. If the first word has a higher rank character than the second, the list is not sorted.
Handle the prefix edge case carefully. If all characters match up to the shorter word but the first word is longer (for example "apple" before "app"), the order is invalid. The algorithm scans each character once across comparisons, so the total time complexity is O(n * m) where n is the number of words and m is the average word length. The mapping structure uses constant space since the alphabet size is fixed (26).
This approach works well with arrays and simple character indexing. It avoids sorting and focuses only on verifying order.
Approach 2: Using Custom Comparator (O(n * m) time, O(1) space)
Another option is to implement a custom comparator that compares two words using the alien character ranking. First build a character-to-rank map similar to the previous approach. Then define a comparison function that iterates through both strings and decides ordering based on the mapped ranks of the first differing characters.
You can use this comparator either to directly check each adjacent pair or to sort a copy of the list and compare it with the original. If the sorted version matches the original sequence, the dictionary was already correctly ordered. Each comparison scans up to the length of the shorter word, giving O(m) per comparison and O(n * m) overall.
This method mirrors how lexicographic comparison works internally in many languages. It is a clean conceptual solution when working with string comparison logic and custom ordering rules stored in a hash table.
Recommended for interviews: The mapping-order approach is what most interviewers expect. It demonstrates that you understand lexicographic comparison and how to translate a custom alphabet into numeric ranks. The custom comparator approach shows good abstraction skills but still relies on the same core idea of character ranking.
Approach 1: Mapping Order Using Indexes
This approach involves converting each character in the alien order to an index, which can be used to easily compare words. The idea is to take the given order of the language and map each character to its position in the order. Then, we can compare words by comparing their mapped indices.
In C, we use an integer array orderIdx to map each character of the alien order to its index. We then compare contiguous words using their mapped indices. If a preceding word is ever greater than a succeeding one, according to the mapped order, we return false.
Complexity
Time Complexity: O(N), where N is the total number of characters in all words. Space Complexity: O(1).
Approach 2: Using Custom Comparator
This approach employs a custom comparator to sort the words based on the alien order. We first map the order and then define a comparator that sorts based on this map. We check if the sorted version of the words matches the original order, indicating that they were sorted correctly in the alien dictionary.
In C, we define a custom comparison function that utilizes the mapped order to determine the lexicographic order of words. We then iterate through the words to ensure they are sorted.
Complexity
Time Complexity: O(N log N) due to sorting. Space Complexity: O(1).
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Mapping Order Using Indexes | Time Complexity: |
| Using Custom Comparator | Time Complexity: |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Mapping Order Using Indexes | O(n * m) | O(1) | Best general solution. Efficiently compares adjacent words using precomputed character ranks. |
| Custom Comparator | O(n * m) | O(1) | Useful when implementing language-style string comparison or sorting with custom ordering. |
Video Solution
Verifying an Alien Dictionary - Leetcode 953 - Python • NeetCode • 41,346 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Verifying an Alien Dictionary easy or hard?
Verifying an Alien Dictionary Python/Java solution
How to solve Verifying an Alien Dictionary in O(n*m)?
What is the best approach for Verifying an Alien Dictionary?
Is Verifying an Alien Dictionary asked at Google/Amazon/Meta?
What data structure is used in Verifying an Alien Dictionary?
What is the time complexity of Verifying an Alien Dictionary?
Ready to solve this problem?
Practice Verifying an Alien Dictionary with our built-in code editor and test cases.
Practice on FleetCode