Scale Engineer

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
ArrayHash TableString
Companies
WixSnap

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' > '∅', where '∅' 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.

class Solution {    public boolean isAlienSorted(String[] words, String order) {        int[] orderMap = new int[26];        for (int i = 0; i < order.length(); i++) {            orderMap[order.charAt(i) - 'a'] = i;        }         for (int i = 0; i < words.length - 1; i++) {            String word1 = words[i];            String word2 = words[i + 1];            int minLength = Math.min(word1.length(), word2.length());            boolean different = false;            for (int j = 0; j < minLength; j++) {                char c1 = word1.charAt(j);                char c2 = word2.charAt(j);                if (c1 != c2) {                    if (orderMap[c1 - 'a'] > orderMap[c2 - 'a']) {                        return false;                    }                    different = true;                    break;                }            }            if (!different && word1.length() > word2.length()) {                return false;            }        }        return true;    }}

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.

Solutions

class 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 ; } }

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 →

Next problem