Verifying an Alien Dictionary

Easy

#0907Time: O(N * M + L), where N is the number of words, M is the maximum length of a word, and L is the length of the `order` string. The pre-computation takes O(L) time. The main comparison loop takes O(N * M) because we iterate through N-1 pairs and each comparison takes at most O(M) time with O(1) character rank lookups. Since L is a constant (26), the complexity is effectively O(N * M).Space: O(L) or O(1), as we use an auxiliary array of size 26 to store the character rankings. Since the alphabet size is fixed, this is considered constant space.2 companies

Data structures

Array Hash Table String

Companies

Wix Snap

Prompt

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' > '&empty;', where '&empty;' is defined as the blank character which is less than any other character (More info).

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
All characters in words[i] and order are English lowercase letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach improves upon the brute-force method by pre-processing the order string. We create a mapping from each character to its rank (position) in the alien alphabet. This allows for constant-time lookups of a character's rank, making the overall comparison process much faster.

Algorithm

Preprocessing: Create an integer array orderMap of size 26. Iterate through the order string and populate orderMap such that orderMap[character - 'a'] stores the rank of the character.
Comparison: Iterate through adjacent pairs of words (word1, word2) in the words array.
Compare word1 and word2 character by character.
For each pair of characters c1 and c2, get their ranks from orderMap in O(1) time.
If rank(c1) > rank(c2), the list is unsorted. Return false.
If rank(c1) < rank(c2), the pair is sorted. Move to the next pair of words.
Handle the prefix case: if word1 is longer than word2 and word2 is a prefix of word1, return false.
If the loop finishes, return true.

Walkthrough

To optimize the character comparison, we can first build a data structure that maps each character to its position in the order string. An array of size 26 is perfect for this, as we are dealing with lowercase English letters. This pre-computation step takes a small, fixed amount of time but allows subsequent character rank lookups to be done in O(1) time, significantly speeding up the main comparison logic.

1class Solution {2    public boolean isAlienSorted(String[] words, String order) {3        int[] orderMap = new int[26];4        for (int i = 0; i < order.length(); i++) {5            orderMap[order.charAt(i) - 'a'] = i;6        }7 8        for (int i = 0; i < words.length - 1; i++) {9            String word1 = words[i];10            String word2 = words[i + 1];11            int minLength = Math.min(word1.length(), word2.length());12            boolean different = false;13            for (int j = 0; j < minLength; j++) {14                char c1 = word1.charAt(j);15                char c2 = word2.charAt(j);16                if (c1 != c2) {17                    if (orderMap[c1 - 'a'] > orderMap[c2 - 'a']) {18                        return false;19                    }20                    different = true;21                    break;22                }23            }24            if (!different && word1.length() > word2.length()) {25                return false;26            }27        }28        return true;29    }30}

Complexity

Time

O(N * M + L), where N is the number of words, M is the maximum length of a word, and L is the length of the `order` string. The pre-computation takes O(L) time. The main comparison loop takes O(N * M) because we iterate through N-1 pairs and each comparison takes at most O(M) time with O(1) character rank lookups. Since L is a constant (26), the complexity is effectively O(N * M).

Space

O(L) or O(1), as we use an auxiliary array of size 26 to store the character rankings. Since the alphabet size is fixed, this is considered constant space.

Trade-offs

Pros

Highly efficient due to O(1) character rank lookups.
The dominant part of the complexity comes from iterating through the words, which is necessary.

Cons

Requires a small amount of extra space for the mapping.

This approach involves iterating through each adjacent pair of words in the input list and comparing them character by character. For each pair of differing characters, we find their positions in the order string using a linear search (indexOf) to determine their relative rank. If we find any pair of words that is out of order, we immediately return false.

Algorithm

Iterate through the words array from i = 0 to words.length - 2.
For each i, take word1 = words[i] and word2 = words[i+1].
Compare word1 and word2 character by character up to the length of the shorter word.
At the first differing character, find their positions in the order string using indexOf().
If the character from word1 has a higher index than the character from word2, the list is unsorted, so return false.
If the character from word1 has a lower index, this pair is sorted. Break the character comparison and check the next pair of words.
If the words are identical up to the length of the shorter word (one is a prefix of the other), check their lengths. If word1 is longer than word2 (e.g., "apple", "app"), the list is unsorted, so return false.
If the entire loop completes, all pairs are sorted correctly. Return true.

Walkthrough

The core idea is to verify the sorted property by checking every two adjacent words. If words[i] should come after words[i+1] for any i, then the array is not sorted. The comparison between two words is done character by character, and the relative order of two different characters is determined by finding their index in the order string.

1class Solution {2    public boolean isAlienSorted(String[] words, String order) {3        for (int i = 0; i < words.length - 1; i++) {4            String word1 = words[i];5            String word2 = words[i + 1];6            int minLength = Math.min(word1.length(), word2.length());7            boolean different = false;8            for (int j = 0; j < minLength; j++) {9                char c1 = word1.charAt(j);10                char c2 = word2.charAt(j);11                if (c1 != c2) {12                    if (order.indexOf(c1) > order.indexOf(c2)) {13                        return false;14                    }15                    different = true;16                    break;17                }18            }19            if (!different && word1.length() > word2.length()) {20                return false;21            }22        }23        return true;24    }25}

Complexity

Time

O(N * M * L), where N is the number of words, M is the maximum length of a word, and L is the length of the `order` string (26). For each of the N-1 pairs of words, we might compare up to M characters. For each character comparison, we perform `indexOf`, which takes O(L) time.

Space

O(1), as we only use a few variables to store indices and characters, not dependent on the input size.

Trade-offs

Pros

Simple to understand and implement.
Requires no extra space.

Cons

Inefficient due to the repeated linear search (indexOf) within the order string for every character comparison.

Solutions

Solution

1class Solution { public boolean isAlienSorted ( String [] words , String order ) { int [] m = new int [ 26 ]; for ( int i = 0 ; i < 26 ; ++ i ) { m [ order . charAt ( i ) - 'a' ] = i ; } for ( int i = 0 ; i < 20 ; ++ i ) { int prev = - 1 ; boolean valid = true ; for ( String x : words ) { int curr = i >= x . length () ? - 1 : m [ x . charAt ( i ) - 'a' ]; if ( prev > curr ) { return false ; } if ( prev == curr ) { valid = false ; } prev = curr ; } if ( valid ) { break ; } } return true ; } }

1class Solution { public: bool isAlienSorted ( vector < string >& words , string order ) { vector < int > m ( 26 ); for ( int i = 0 ; i < 26 ; ++ i ) m [ order [ i ] - 'a' ] = i ; for ( int i = 0 ; i < 20 ; ++ i ) { int prev = - 1 ; bool valid = true ; for ( auto & x : words ) { int curr = i >= x . size () ? - 1 : m [ x [ i ] - 'a' ]; if ( prev > curr ) return false ; if ( prev == curr ) valid = false ; prev = curr ; } if ( valid ) break ; } return true ; } };

1class Solution : def isAlienSorted ( self , words : List [ str ], order : str ) -> bool : m = { c : i for i , c in enumerate ( order )} for i in range ( 20 ): prev = - 1 valid = True for x in words : curr = - 1 if i >= len ( x ) else m [ x [ i ]] if prev > curr : return False if prev == curr : valid = False prev = curr if valid : return True return True

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem