Leetcode – Verifying an Alien Dictionary Solution in Python

Spread the love

One of the most intriguing challenges in the domain of string manipulation and comparison is the “Verifying an Alien Dictionary” problem. In this comprehensive article, we aim to unpack the problem, delve deep into its nuances, and present a structured Python-based solution.

Problem Statement

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, your task is to return true if and only if the given words are sorted lexicographically in this alien language.

Understanding the Problem

The primary challenge in this problem lies in the altered lexicographical order. We need to devise a method to compare the words based on this new order and verify if they are sorted.

Key Insight

If we can map each alien character to its position in the alien dictionary and then translate the given words into a format understandable by us (based on our standard dictionary), the task reduces to just checking if the words are sorted in our language.

Algorithm to Solve the Problem

  1. Create a mapping of each character in the order string to its index.
  2. Convert the given words list into a new list based on the alien dictionary order.
  3. Check if the newly formed list is sorted. If it is, then the original list is sorted based on the alien dictionary.

Python Code Solution

Let’s implement the solution based on the outlined algorithm:

def isAlienSorted(words, order):
    # Create a mapping from the 'order' string
    mapping = {char: i for i, char in enumerate(order)}

    # Translate the words into a new format based on the alien dictionary
    translated_words = [[mapping[char] for char in word] for word in words]

    # Check if the new list of words is sorted
    for i in range(1, len(translated_words)):
        if translated_words[i-1] > translated_words[i]:
            return False
    return True

Complexity Analysis

  • Time Complexity: O(N) – Where N is the total number of characters across all words. We traverse through each character once while translating and then once more to check if the translated words are sorted.
  • Space Complexity: O(1) – Although we create a new list of translated words, the space used is directly proportional to the input size, which is O(N). The space used for the mapping dictionary is constant, O(26) or O(1), because there are only 26 lowercase English letters.

Testing the Solution

It’s imperative to validate the solution across diverse test cases:

print(isAlienSorted(["hello", "leetcode"], "hlabcdefgijkmnopqrstuvwxyz"))  # Expected output: True
print(isAlienSorted(["word", "world", "row"], "worldabcefghijkmnpqstuvxyz")) # Expected output: False
print(isAlienSorted(["apple", "app"], "abcdefghijklmnopqrstuvwxyz"))        # Expected output: False

Conclusion

The “Verifying an Alien Dictionary” problem, like many on Leetcode, encourages one to think beyond the obvious and find creative solutions to seemingly complex challenges. By mapping an alien dictionary to our known lexicographical order, we reduce the problem’s complexity, allowing for a more intuitive solution.

Leave a Reply