Solution: Verifying an Alien Dictionary

Statement

You’re given a list of words with lowercase English letters in a different order, written in an alien language. The order of the alphabet is some permutation of lowercase letters of the English language.

We have to return TRUE if the given list of words is sorted lexicographically in this alien language.

Constraints:

• $1 \leq$ words.length $\leq 10^3$
• $1 \leq$ words[i].length $\leq 20$
• order.length $== 26$
• All the characters in words[i] and order are lowercase English letters.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which to follow based on considerations such as time complexity and implementation constraints.

Naive approach

The naive approach for this problem is to iterate over the order list and words simultaneously. Start from the first word, then compare the order with all other words present in the list.

The time complexity for the naive approach is $O(n^3)$, since we’re iterating the order list and the complete list two times in nested loops. The space complexity of this naive approach is constant because we didn’t use any extra memory.

Optimized approach using topological sort

We can solve this problem using the topological sort pattern. Topological sort is used to find a linear ordering of elements that depend on or prioritize each other. For example, if A depends on B or if B has priority over A, B is listed before A in topological order.

For this problem, we’re given the list of words and the order of the alphabet. Using the order of the alphabet, we must check if the list of words is sorted lexicographically.

We can check adjacent words to see if they are in the correct order. For each word, the word on its right should be lexicographically larger, and the one on its left should be lexicographically smaller.

One thing to notice here is that we don’t need to compare all the words. We can just compare each pair of adjacent words instead. If all the pairs of adjacent words are in order, we can safely assume that the integrity is intact. Conversely, if any pair of adjacent words isn’t in order, we can assume that our order is not correct.

Let’s review the illustration to better understand the intuition described above with the help of a sample list of three words, $[w1, w2, w3]$: