0953. Verifying an Alien Dictionary

Easy | String + Hash Table | 28 ms (96.12%), 14.2 MB (91.25%)

❓ Problem Statement

Source: LeetCode - Verifying an Alien Dictionary GitHub: Solution / Performance

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.

✍🏻 Constraints & Example

Constraints:

• 1 <= words.length <= 100

• 1 <= words[i].length <= 20

• order.length == 26

• All characters in words[i] and order are English lowercase letters.

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: 
    As 'h' comes before 'l' in this language, then the sequence is sorted.

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.

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.

💡 Ideas

Lexicographical order in English 1. Correct order for [apple, book] 2. Correct order for [backtrack, backwords] 3. Wrong order for [apple, app]. Should be [app, apple]

First, we build the order using the hash table or array according to the input order. Then, we iterate through each word in the words to check it with the adjacent word.

Check Conditions

1. Current index + 1 (current length) is larger than next word's length, return False For the first iteration (index = 0), this check does not work since each word has 1 as MIN length. After passing the first iteration with second check, this check will be effective.

2. Current word and the adjacent word have different char in the same index

   • Check their order, if violate, return False.

   • Otherwise, break to the next iteration (since they are in the correct order).

🤖 Python3

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        
        # ==================================================
        #  String                                          =
        # ==================================================
        # time  : O(M), M is the total number of chars in words
        # space : O(1)
        
        table = dict()
        for i in range(len(order)): table[order[i]] =  i
            
        for i in range(len(words) - 1):
            for j in range(len(words[i])):
                # (current string's length > adjacent string's length)
                if j+1 > len(words[i+1]): return False
                
                if words[i][j] != words[i+1][j]:
                    if table[words[i][j]] > table[words[i+1][j]]: return False
                    break
                    
        return True

🤖 Java

class Solution {
    /**
     * @time  : O(M), M is the total number of chars in words
     * @space : O(1)
     */
    
    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++) {
            for (int j=0; j<words[i].length(); j++) {
                /* 
                    If we do not find a mismatch letter between words[i] and words[i + 1],
                    we need to examine the case when words are like ("apple", "app").
                */
                if (j+1 > words[i+1].length()) return false;

                if (words[i].charAt(j) != words[i+1].charAt(j)) {
                    int currentWordChar = words[i].charAt(j) - 'a';
                    int nextWordChar = words[i+1].charAt(j) - 'a';
                    
                    if (orderMap[currentWordChar] > orderMap[nextWordChar]) return false;
                    
                    /* 
                        If we find the first different letter and they are sorted,
                        then there's no need to check remaining letters
                    */
                    else break;
                }
            }
        }

        return true;
    }
}