Naive Approach

The most straightforward approach is to iterate through the words list and compare each pair of adjacent words to determine if they are in the correct order according to the given alien alphabet order. This involves checking character by character until a difference is found or one of the words runs out of characters.

Algorithm

1. Create a mapping (e.g., a dictionary or array) from each character in order to its index (priority) in the alien alphabet.
2. Iterate through the words list from the first word to the second to last word.
3. For each pair of adjacent words, compare them character by character.
4. If a character in the first word is "greater" (has a higher priority) than the corresponding character in the second word, return false.
5. If a character in the first word is "less" than the corresponding character in the second word, move on to the next pair of words.
6. If the words are identical up to the length of the shorter word and the first word is longer, return false.
7. If all pairs of words are in the correct order, return true.

Code (Python)

def isAlienSorted_naive(words, order):
    order_map = {char: i for i, 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]]:
                return False
            elif order_map[word1[j]] < order_map[word2[j]]:
                break  # words are in order, check next pair
        else:
            # If all characters are same up to the min length, check length
            if len(word1) > len(word2):
                return False  # word1 is longer, so out of order

    return True

Time Complexity

O(N * M), where N is the number of words and M is the average length of the words. In the worst case, we compare each character of each word.

Space Complexity

O(1). The order_map uses a fixed amount of space (26 characters).

Optimal Approach

The optimal approach is essentially the same as the naive approach, but with cleaner code and potentially minor optimizations. The core idea of comparing adjacent words based on the provided alien order remains unchanged.

Algorithm

1. Create an order map (dictionary) to store the index (priority) of each character in the alien alphabet.
2. Define a helper function compare_words(word1, word2, order_map) to compare two words.
3. In the compare_words function, iterate through the characters of both words up to the length of the shorter word.
4. If characters at a given index differ, compare their priorities using the order map. If word1 character has higher priority, return false. If word2 character has higher priority, return true.
5. If all characters up to the length of the shorter word are identical, return true if word1 is shorter or equal in length to word2, and false otherwise.
6. Iterate through the words array and compare each pair of adjacent words using the compare_words function.
7. Return false if any pair is out of order; otherwise, return true.

Code (Python)

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

    def compare_words(word1, word2, order_map):
        min_len = min(len(word1), len(word2))
        for i in range(min_len):
            if order_map[word1[i]] > order_map[word2[i]]:
                return False
            elif order_map[word1[i]] < order_map[word2[i]]:
                return True
        return len(word1) <= len(word2)

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

    return True

Time Complexity

O(N * M), where N is the number of words and M is the average length of the words.

Space Complexity

O(1). The order_map uses a fixed amount of space (26 characters).

Edge Cases

• Empty input words list: Should return true because an empty list is considered sorted.
• Single word in the words list: Should return true as a single element is always sorted.
• Empty words: The algorithm handles this correctly as the minimum length will be 0, and it will proceed correctly based on lengths.
• Identical words: The algorithm correctly handles identical words as it checks the lengths in case one word is a prefix of the other.