Verifying An Alien Dictionary - Leetcode Solution

Problem Statement:

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 lexicographicaly in this alien language.

Example 1: Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz" Output: true Explanation: As 'h' comes before 'l' in the given order. "hello" precedes "leetcode" in lexicographically order.

Example 2: Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz" Output: false Explanation: As the order of 'd' and 'l' is not defined in the given order. So "word" and "world" cannot be compared.

Example 3: Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz" Output: false Explanation: The first three characters "app" match but the string "apple" is bigger than "app" because 'l' comes after 'e' in the given order.

Approach:

We can take the given order and create a dictionary that stores the position of each letter in the order. Then, we can compare each word in the given list with its next word. If at any point we find that the current word is greater than the next word, we can return False, as it violates the lexicographical order.

Steps:

1. Create a dictionary for the given order, where the key is the letter and the value is its position in the order.
2. Compare each word in the given list with its next word to check if they are sorted lexicographically using the dictionary created in step 1.
3. If we find that the current word is greater than the next word, return False. If we can loop through the entire list, it means they are sorted lexicographically, so return True.

Code:

The following code implements the above approach for the given problem.

class Solution: def isAlienSorted(self, words: List[str], order: str) -> bool: order_map = {} for i, c in enumerate(order): order_map[c] = i

    for i in range(len(words)-1):
        word1 = words[i]
        word2 = words[i+1]
        
        for j in range(min(len(word1), len(word2))):
            if word1[j] != word2[j]:
                if order_map[word1[j]] > order_map[word2[j]]:
                    return False
                break
            
        else:
            if len(word1) > len(word2):
                return False
            
    return True

Time Complexity: O(NK), where N is the number of words in the given list and K is the average length of each word in the list.

Space Complexity: O(26) = O(1), as we are using a fixed size dictionary for the given order.

1