Verifying an Alien Dictionary

Easy

Google

0 views

Topics:

ArraysStringsTwo Pointers

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, determine if the given words are sorted lexicographically in this alien language.

Example 1:

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

Example 2:

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:

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.

Write a function to solve this problem. The function should take a list of strings words and a string order as input and return a boolean value indicating whether the words are sorted lexicographically according to the given order.

Verifying an Alien Dictionary

Easy

Google

0 views

Topics:

ArraysStringsTwo Pointers

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, determine if the given words are sorted lexicographically in this alien language.

Example 1:

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

Example 2:

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:

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.

Solution

Naive Solution

A brute force solution would be to iterate through the words array and compare each word with the next word using the given order. For each pair of words, we compare characters until we find a difference or reach the end of one of the words. If we find a pair of words that are not in lexicographical order according to the order string, we return false. Otherwise, we continue checking until we have checked all pairs, and then return true.

Edge Cases

Empty words array: Should return true.
words array with only one word: Should return true.
One word is a prefix of another: Handle the case where one word is a prefix of another. For example, "apple" and "app". "app" should come before "apple".

Code

def isAlienSortedNaive(words: list[str], order: str) -> bool:
    order_map = {char: index for index, char in enumerate(order)}

    for i in range(len(words) - 1):
        word1, word2 = words[i], words[i + 1]
        min_len = min(len(word1), len(word2))

        for j in range(min_len):
            if order_map[word1[j]] < order_map[word2[j]]:
                break  # word1 comes before word2, continue to next pair
            elif order_map[word1[j]] > order_map[word2[j]]:
                return False  # word1 comes after word2, not sorted
        else:
            # If we reach here, it means one word is a prefix of the other
            if len(word1) > len(word2):
                return False  # word1 is longer and should come after

    return True

Time Complexity

O(N * M), where N is the number of words and M is the average length of the words. We iterate through the words array once, and for each pair of words, we compare characters up to the length of the shorter word.

Space Complexity

O(1), since we use a fixed amount of extra space to store the order_map, regardless of the input size (in reality O(26) since order is always 26 chars).

Optimal Solution

The optimal solution is essentially the same as the naive solution, as we need to compare each pair of words to determine if they are in lexicographical order according to the given order. Therefore the naive solution already is the optimal one.

Code

def isAlienSorted(words: list[str], order: str) -> bool:
    order_map = {char: index for index, char in enumerate(order)}

    for i in range(len(words) - 1):
        word1, word2 = words[i], words[i + 1]
        min_len = min(len(word1), len(word2))

        for j in range(min_len):
            if order_map[word1[j]] < order_map[word2[j]]:
                break  # word1 comes before word2, continue to next pair
            elif order_map[word1[j]] > order_map[word2[j]]:
                return False  # word1 comes after word2, not sorted
        else:
            # If we reach here, it means one word is a prefix of the other
            if len(word1) > len(word2):
                return False  # word1 is longer and should come after

    return True

Time Complexity

Space Complexity

O(1), since we use a fixed amount of extra space to store the order_map, regardless of the input size (in reality O(26) since order is always 26 chars).

Solution

Naive Solution

Edge Cases

Empty words array: Should return true.
words array with only one word: Should return true.
One word is a prefix of another: Handle the case where one word is a prefix of another. For example, "apple" and "app". "app" should come before "apple".

Code

def isAlienSortedNaive(words: list[str], order: str) -> bool:
    order_map = {char: index for index, char in enumerate(order)}

    for i in range(len(words) - 1):
        word1, word2 = words[i], words[i + 1]
        min_len = min(len(word1), len(word2))

        for j in range(min_len):
            if order_map[word1[j]] < order_map[word2[j]]:
                break  # word1 comes before word2, continue to next pair
            elif order_map[word1[j]] > order_map[word2[j]]:
                return False  # word1 comes after word2, not sorted
        else:
            # If we reach here, it means one word is a prefix of the other
            if len(word1) > len(word2):
                return False  # word1 is longer and should come after

    return True

Time Complexity

Space Complexity

O(1), since we use a fixed amount of extra space to store the order_map, regardless of the input size (in reality O(26) since order is always 26 chars).

Optimal Solution

Code

def isAlienSorted(words: list[str], order: str) -> bool:
    order_map = {char: index for index, char in enumerate(order)}

    for i in range(len(words) - 1):
        word1, word2 = words[i], words[i + 1]
        min_len = min(len(word1), len(word2))

        for j in range(min_len):
            if order_map[word1[j]] < order_map[word2[j]]:
                break  # word1 comes before word2, continue to next pair
            elif order_map[word1[j]] > order_map[word2[j]]:
                return False  # word1 comes after word2, not sorted
        else:
            # If we reach here, it means one word is a prefix of the other
            if len(word1) > len(word2):
                return False  # word1 is longer and should come after

    return True

Time Complexity

Space Complexity

O(1), since we use a fixed amount of extra space to store the order_map, regardless of the input size (in reality O(26) since order is always 26 chars).