Code Implementation

class Solution:
    def isAlienSorted(self, words, order):
        # Build a mapping from character to its order index
        order_index = {char: idx for idx, char in enumerate(order)}
        
        def in_correct_order(w1, w2):
            # Compare two words
            for c1, c2 in zip(w1, w2):
                if c1 != c2:
                    return order_index[c1] < order_index[c2]
            # If all characters are the same up to the length of the shorter word
            return len(w1) <= len(w2)
        
        # Check each adjacent pair
        for i in range(len(words) - 1):
            if not in_correct_order(words[i], words[i+1]):
                return False
        return True
      

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        vector<int> orderIndex(26);
        for (int i = 0; i < order.size(); ++i)
            orderIndex[order[i] - 'a'] = i;
        
        auto inCorrectOrder = [&](const string& w1, const string& w2) {
            int n = min(w1.size(), w2.size());
            for (int i = 0; i < n; ++i) {
                if (w1[i] != w2[i])
                    return orderIndex[w1[i] - 'a'] < orderIndex[w2[i] - 'a'];
            }
            return w1.size() <= w2.size();
        };
        
        for (int i = 0; i < words.size() - 1; ++i) {
            if (!inCorrectOrder(words[i], words[i+1]))
                return false;
        }
        return true;
    }
};
      

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] orderIndex = new int[26];
        for (int i = 0; i < order.length(); ++i)
            orderIndex[order.charAt(i) - 'a'] = i;
        
        for (int i = 0; i < words.length - 1; ++i) {
            if (!inCorrectOrder(words[i], words[i+1], orderIndex))
                return false;
        }
        return true;
    }
    
    private boolean inCorrectOrder(String w1, String w2, int[] orderIndex) {
        int n = Math.min(w1.length(), w2.length());
        for (int i = 0; i < n; ++i) {
            char c1 = w1.charAt(i), c2 = w2.charAt(i);
            if (c1 != c2)
                return orderIndex[c1 - 'a'] < orderIndex[c2 - 'a'];
        }
        return w1.length() <= w2.length();
    }
}
      

var isAlienSorted = function(words, order) {
    const orderIndex = {};
    for (let i = 0; i < order.length; ++i)
        orderIndex[order[i]] = i;
    
    function inCorrectOrder(w1, w2) {
        let n = Math.min(w1.length, w2.length);
        for (let i = 0; i < n; ++i) {
            if (w1[i] !== w2[i])
                return orderIndex[w1[i]] < orderIndex[w2[i]];
        }
        return w1.length <= w2.length;
    }
    
    for (let i = 0; i < words.length - 1; ++i) {
        if (!inCorrectOrder(words[i], words[i+1]))
            return false;
    }
    return true;
};
      

Problem Description

Given a list of words words written in an alien language, and a string order representing the order of the alphabet in this alien language, determine if the list of words is sorted lexicographically according to this new alien order.

• Each word consists of lowercase English letters, but their order is defined by order.
• You must check if words appears in sorted order as per the alien alphabet.
• There is always a unique possible order, and you do not need to handle ties or ambiguity.
• Do not modify or reorder the input; simply return true or false.

Thought Process

At first glance, this problem looks like a classic "is array sorted?" check, but with a twist: the comparison between letters isn't the standard English alphabet, but a custom order.

The brute force approach would be to compare every pair of adjacent words using the given order, letter by letter. However, we need a way to quickly look up the position of each character in the alien alphabet.

To optimize, we can create a mapping from each character to its index in the alien order string. This lets us compare two letters in constant time. Then, for each adjacent pair of words, we compare their letters one by one using this mapping, stopping as soon as we find a difference.

If all pairs are in the correct order, the list is sorted; otherwise, it is not.

Solution Approach

• Step 1: Build a mapping.
  • Create a map (or array) that assigns each character in order to its index. For example, if order[0] = 'h', then order_index['h'] = 0.
• Step 2: Compare adjacent words.
  • For each pair of consecutive words in words, compare them character by character.
  • If the letters are different, use the mapping to determine which comes first. If the first word's letter comes after the second's, return false.
  • If all letters are the same up to the length of the shorter word, the shorter word should come first (or be equal in length).
• Step 3: Return result.
  • If all word pairs are in the correct order, return true.

Using a mapping allows us to compare characters efficiently, and iterating through adjacent pairs ensures we only do the minimum work needed.

Example Walkthrough

Let's use the following example:

• words = ["hello", "leetcode"]
• order = "hlabcdefgijkmnopqrstuvwxyz"

Step-by-step:

1. Build the order_index mapping, so 'h' is 0, 'l' is 1, 'a' is 2, etc.
2. Compare "hello" and "leetcode":
3. - First letters: 'h' vs 'l'. order_index['h'] = 0, order_index['l'] = 1.
   - Since 0 < 1, "hello" comes before "leetcode" in alien order.
4. - Since this pair is in order, and there are no more pairs, we return true.

If the first letters were equal, we would continue comparing the next letters, and so on, until a difference is found or one word ends.

Time and Space Complexity

• Brute-force:
  • Comparing every possible pair of words would be O(N^2 * L), where N is the number of words and L is the average word length.
• Optimized approach:
  • We only compare adjacent pairs, so the time complexity is O(N * L).
  • Building the mapping is O(1), since order has a fixed length of 26.
  • Space complexity is O(1) for the mapping (since there are only 26 characters).

Thus, the optimized solution is efficient and suitable for large inputs.

Summary

The key insight is to use a mapping from characters to their alien order index, allowing fast letter-by-letter comparisons. By checking each adjacent pair of words, we efficiently determine if the list is sorted according to the alien dictionary. This approach is both simple and efficient, making it ideal for this type of custom sorting problem.