#953

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Verifying an Alien Dictionary

Verify if a sequence of words is sorted according to an alien language's custom alphabet order using array scanning and hash lookups.

array hash table string

Problem Statement

In an alien language, the alphabet consists of the same lowercase letters used in English, but the order of the letters might differ. You are given a list of words written in this alien language and a string representing the order of the alphabet. Your task is to verify if the sequence of words is sorted lexicographically according to the alien alphabet.

For example, given the words ['hello', 'leetcode'] and the order of the alphabet 'hlabcdefgijkmnopqrstuvwxyz', the words are considered sorted because 'h' comes before 'l'. However, in cases like ['apple', 'app'], the sequence is unsorted because the second string is shorter but should have been lexicographically greater.

Examples

Example 1

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"

Output: true

As 'h' comes before 'l' in this language, then the sequence is sorted.

Example 2

Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"

Output: false

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

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.

Solution Approach

Map Alphabet to Indices

The first step is to create a hash table to map each character in the alien alphabet to its respective index. This allows you to compare characters efficiently in constant time during word comparisons.

Iterate and Compare Adjacent Words

Next, iterate through the list of words, comparing each word with the next one in sequence. For each pair of adjacent words, compare them character by character. If at any point the first word is greater than the second based on the alien alphabet, return false.

Handle Edge Cases

Edge cases include situations where one word is a prefix of another. For example, 'apple' and 'app' are in the wrong order in the given alphabet, as the shorter word should come after the longer one in lexicographical order.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this approach is O(n * m), where n is the number of words and m is the average length of the words. This is because we compare each word to the next one, character by character. The space complexity is O(1) if we assume that the order string's length is constant (26 characters), otherwise it is O(k), where k is the number of unique characters in the alien alphabet map.

What Interviewers Usually Probe

Is the candidate able to efficiently map the alien alphabet?
Can they identify and handle edge cases such as prefix issues?
Does the candidate approach the problem with an array scanning and hash table solution, avoiding unnecessary complexity?

Common Pitfalls or Variants

Common pitfalls

Not properly handling cases where a word is a prefix of another (e.g., 'apple' vs 'app').
Failing to correctly implement the lexicographical comparison using the alien alphabet's custom order.
Overcomplicating the solution by not recognizing the optimal approach using array scanning and hash lookups.

Follow-up variants

What if the list of words is very large? Can the algorithm still scale efficiently?
How would the solution change if we were given words in reverse order?
Can we solve the problem without using a hash table, and if so, what would the time complexity be?

FAQ

What is the pattern used to solve the 'Verifying an Alien Dictionary' problem?

The solution leverages array scanning combined with hash lookups to compare adjacent words in the sequence efficiently based on the custom alien alphabet order.

How do I handle cases where one word is a prefix of another?

When a word is a prefix of another, ensure the longer word comes after the shorter one lexicographically, which means the shorter word should not appear before the longer one if they are equal up to the prefix.

What is the time complexity of the solution for this problem?

The time complexity is O(n * m), where n is the number of words and m is the average length of the words, because each word needs to be compared to the next word character by character.

How can I improve the solution if there are many words?

The current solution is already optimal in terms of time complexity, but ensuring that the word comparison step is as fast as possible using hash lookups is key to scaling for large inputs.

What if the alien alphabet order is not provided in the form of a string?

You would need to transform the input format into a hash table or array representation that maps each character to its index in the alien alphabet for efficient comparison.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class 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

Continue Practicing

#966 vowel spellchecker #929 unique email addresses #916 word subsets