Verifying an Alien Dictionary Interview Question for Google

def isAlienSorted(words, order):
    """
    Given a sequence of words written in an 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 1:
    Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
    Output: true
    Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

    Example 2:
    Input: 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:
    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 rules "apple" > "app", because 'l' > '', where '' is defined as the blank character which is less than any other character (More info).

    Args:
        words (list[str]): A list of words in the alien language.
        order (str): The order of the alphabet in the alien language.

    Returns:
        bool: True if the words are sorted lexicographically, False otherwise.
    """

    # Create a dictionary to map each character in the alien alphabet to its index.
    order_map = {char: index for index, char in enumerate(order)}

    # Iterate over the words, comparing each word to the next.
    for i in range(len(words) - 1):
        word1 = words[i]
        word2 = words[i + 1]

        # Compare the words character by character.
        for j in range(min(len(word1), len(word2))):
            char1 = word1[j]
            char2 = word2[j]

            if order_map[char1] < order_map[char2]:
                # If the characters are in the correct order, move on to the next word.
                break
            elif order_map[char1] > order_map[char2]:
                # If the characters are in the wrong order, the words are not sorted.
                return False
        else:
            # If we reach the end of the inner loop, it means that the words are equal up to the length of the shorter word.
            # In this case, the shorter word should come first.
            if len(word1) > len(word2):
                return False

    # If we reach the end of the outer loop, it means that all the words are sorted.
    return True

# Example usage:
words1 = ["hello", "leetcode"]
order1 = "hlabcdefgijkmnopqrstuvwxyz"
print(isAlienSorted(words1, order1))  # Output: True

words2 = ["word", "world", "row"]
order2 = "worldabcefghijkmnpqstuvxyz"
print(isAlienSorted(words2, order2))  # Output: False

words3 = ["apple", "app"]
order3 = "abcdefghijklmnopqrstuvwxyz"
print(isAlienSorted(words3, order3))  # Output: False

Brute Force Solution

The provided solution can be considered as a brute-force approach because it directly compares each pair of consecutive words based on the given alien alphabet order. It iterates through the words and compares them character by character until a difference is found or one of the words is exhausted.

Optimal Solution

The provided solution is already optimized in terms of time complexity. It achieves the desired result by comparing words character by character based on the custom alphabet order. There are no unnecessary or redundant steps in the algorithm.

Big(O) Run-time Analysis

The time complexity of the isAlienSorted function can be analyzed as follows:

Creating the order_map dictionary: This step involves iterating through the order string once, which takes O(26) time since order always contains 26 characters (lowercase English letters). This is effectively O(1) because it's constant time.
Iterating through the words list: The outer loop iterates through the words list from index 0 to len(words) - 1. If there are n words in the input list, this loop runs n - 1 times, which is O(n).
Comparing the words: The inner loop compares the characters of two words, word1 and word2, character by character. In the worst case, it compares up to the length of the shorter word. Let k be the average length of the words in the input list. Then, the inner loop runs up to k times on average, which is O(k).

Inside the inner loop, the code accesses the order_map dictionary using the characters from the words. Dictionary lookups take O(1) time on average.

Therefore, the overall time complexity of the algorithm is O(n * k), where n is the number of words in the input list, and k is the average length of the words.

Big(O) Space Usage Analysis

The space complexity of the isAlienSorted function can be analyzed as follows:

order_map Dictionary: The function creates a dictionary called order_map to store the index of each character in the alien alphabet. Since there are 26 characters in the English alphabet, the order_map dictionary will store 26 key-value pairs. Therefore, the space required for order_map is O(26), which is effectively O(1) because it's constant space.
Other Variables: The function uses a few other variables such as word1, word2, char1, and char2 to store the words and characters being compared. These variables take up a constant amount of space, so they don't affect the overall space complexity.

Therefore, the overall space complexity of the algorithm is O(1) because the space required for the order_map dictionary is constant regardless of the input size.

Edge Cases

Here are some edge cases that can occur with this problem and how the provided code handles them:

Empty input list: If the input list of words is empty, the code will not enter the outer loop, and it will return True because an empty list is considered sorted.
Single word in the input list: If the input list contains only one word, the code will not enter the outer loop because it requires at least two words to compare. In this case, it will return True because a single-word list is considered sorted.
Words with different lengths: The code correctly handles words with different lengths by comparing them character by character up to the length of the shorter word. If one word is a prefix of another (e.g., "apple" and "app"), the code checks if the shorter word comes before the longer word.
Identical words: If the input list contains identical words, the code will correctly handle them because it will compare the words character by character, and if they are the same, it will move on to the next pair of words.
Invalid input: The problem statement specifies that the input words and order contain only lowercase English letters. The code assumes that the input is valid and does not perform any additional input validation.
order string with length other than 26: The problem statement says that order has length 26. If it is a different length, the code will raise an exception when trying to access order_map[char1] or order_map[char2], since some letters will be missing.