def verify_alien_dictionary(words, order):
    # If there is only one word to check, this is a trivial case with 
    # not enough input (minimum two words) to run the algorithm. 
    # So we return True
    if len(words) == 1:
        return True
    # Declare a hash map to store the characters of the words
    order_map = {}
    # Traverse order and store the rank of each letter in order_map
    for index, val in enumerate(order): 
        order_map[val] = index
    # Traverse in array words
    for i in range(len(words) - 1):
        # Traverse each character in a word
        for j in range(len(words[i])):
            # If all the letters have matched so far, but the current word
            # is longer than the next one, the two are not in order and
            # we return False
            if j >= len(words[i + 1]):
                return False
            # Check if the letters in the same position in the two words 
            # are different
            if words[i][j] != words[i + 1][j]:
                # Check if the rank of the letter in the current word is 
                # greater than the rank in the same position in the next word
                if order_map[words[i][j]] > order_map[words[i + 1][j]]:
                    return False
                # if we find the first different character and they are sorted,
                # then there's no need to check remaining letters
                break
    return True

# Driver Code
def main():
    words = [
      ["alpha", "bravo", "charlie", "delta"], 
      ["apple", "app"], 
      ["martian"], 
      ["jupyter", "ascending"], 
      ["passengers", "to", "the", "unknown"]
    ]

    order = ["abcdefghijklmnopqrstuvwxyz", "abcdefghijklmnopqrstuvwxyz", "mabcdefghijklnopqrstuvwxyz", 
    "jabcdefghiklmnopqrstuvwxyz", "ptuhabcdefghijklmnoqrsvwxyz"]

    for i in range(len(order)):
        print(i + 1, ".\tWords: ", words[i], sep="")
        print("\tOrder: \"", order[i], "\"", sep="")
        result = verify_alien_dictionary(words[i], order[i])
        if result:
            print("\tAlien dictionary verified: Yes")
        else:
            print("\tAlien dictionary verified: No")
        print("-"*100)


if __name__ == '__main__':
    main()