Introduction

In this blog post, we will explore how to solve the LeetCode problem "953" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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, 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). Constraints: 1 <= words.length <= 100 1 <= words[i].length <= 20 order.length == 26 All characters in words[i] and order are English lowercase letters.

Explanation

• Establish Alphabet Order: Create a mapping (e.g., a dictionary) from each character in the order string to its index (priority) in the alien alphabet.
  • Lexicographical Comparison: Iterate through the words array, comparing each consecutive pair of words to see if they are in the correct order according to the alien alphabet. Implement a helper function to compare two words character by character, using the alphabet mapping.
  • Handle Prefix Case: Correctly handle the case where one word is a prefix of the other. The longer word should come after the prefix.

• 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) - since the alphabet size is fixed at 26.

Code

    def isAlienSorted(words: list[str], order: str) -> bool:
    """
    Checks if the given words are sorted lexicographically in the alien language.

    Args:
        words: A list of words written in the alien language.
        order: A string representing the order of the alien alphabet.

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

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

    def compare_words(word1: str, word2: str) -> bool:
        """
        Compares two words based on the alien alphabet order.

        Returns:
            True if word1 <= word2, False otherwise.
        """
        len1, len2 = len(word1), len(word2)
        for i in range(min(len1, len2)):
            char1, char2 = word1[i], word2[i]
            if char1 != char2:
                return order_map[char1] < order_map[char2]

        # Handle the case where one word is a prefix of the other.
        return len1 <= len2

    # Iterate through the words and compare each consecutive pair.
    for i in range(len(words) - 1):
        if not compare_words(words[i], words[i + 1]):
            return False

    return True