Verifying an Alien Dictionary

EASY

Description

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

Checkout 2 different approaches to solve Verifying an Alien Dictionary. Click on different approaches to view the approach and algorithm in detail.

Comparison with Pre-computed Order Map

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.

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 Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Verifying an Alien Dictionary. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Verifying an Alien Dictionary

Data Structures:

ArrayHash TableString

Companies:

Wix |Snap |