Verifying an Alien Dictionary - Video Solutions

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.