algoadvance

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:

Example 1:

• Input: words = [“hello”,”leetcode”], order = “hlabcdefgijkmnopqrstuvwxyz”
• Output: true
• Explanation: As ‘h’ comes before ‘l’ in this language, the sequence is sorted.

Example 2:

• Input: words = [“word”,”world”,”row”], order = “worldabcefghijkmnpqstuvxyz”
• Output: false
• Explanation: As ‘d’ comes after ‘l’ in this language, the sequence is not sorted.

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 order “apple” should come after “app”.

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 20
• order.length == 26
• All characters in words[i] and order are English lowercase letters.

Clarifying Questions

1. Will the input words always contain only lowercase English letters?
   • Yes, the problem constraints ensure that only lowercase English letters are used in the words and the order.
2. Will there be any duplicate words or characters in the words list?
   • There can be duplicate words in the list, but it does not affect the lexicographical ordering check.

Strategy

1. Mapping the Order:
   • Create a dictionary to map each character in the order string to its positional index (0 to 25).
2. Compare Words:
   • Iterate through each pair of adjacent words and compare them using the alien dictionary order.
   • For each pair of words, compare character by character.
     • If characters are different, use the order dictionary to determine which word should come first.
     • If one word is a prefix of the other, ensure that the shorter word comes first.
3. Edge Cases:
   • Handle cases where words are exactly the same or one is a prefix of the other.

Code

def isAlienSorted(words, order):
    order_index = {char: i for i, char in enumerate(order)}

    def compare_words(word1, word2):
        for c1, c2 in zip(word1, word2):
            if c1 != c2:
                return order_index[c1] < order_index[c2]
        return len(word1) <= len(word2)

    for i in range(len(words) - 1):
        if not compare_words(words[i], words[i + 1]):
            return False
    return True

Time Complexity

The time complexity of this solution is O(N * M), where:

• N is the number of words.
• M is the maximum length of a word in the list.

Explanation:

• Creating the order index dictionary takes O(26) = O(1) since the length of the alphabet is constant.
• Comparing each pair of words takes O(M).
• We compare N-1 pairs of words in total.

Thus, the overall time complexity is O(N * M).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?