Verifying an Alien Dictionary

How it works

For a list to be sorted, each adjacent pair must be in the correct order. Instead of sorting, we can directly verify that each word is lexicographically less than or equal to the next word according to the alien order. This avoids the overhead of sorting.

Steps

1. Create a mapping from each character to its index position in the order string.
2. Iterate through adjacent pairs of words (w1, w2) in the array.
3. Compare characters at each position until a difference is found or one word ends.
4. If w1 is longer than w2 and all compared characters match, return false (prefix violation).
5. If characters differ, check that w1's character has a smaller index than w2's character in alien order. If not, return false.
6. If all adjacent pairs pass validation, return true.

Complexity

• Time complexity: O(n * m)
• Space complexity: O(1) since we have 26 different characters.

Where n is the number of words and m is the average length of a word.

Things to watch for

Ignoring the Prefix Case

When comparing two words where one is a prefix of the other (e.g., "apple" and "app"), the shorter word must come first. If the longer word appears before its prefix in the list, the order is invalid. Many solutions forget to check this case and only compare differing characters.

Breaking Too Early or Too Late in Character Comparison

When comparing adjacent words character by character, you must break out of the loop as soon as you find the first differing character. Continuing to compare after finding a difference can lead to incorrect conclusions, as only the first difference determines the relative order of two words.

from typing import List

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        order_index = {c: i for i, c in enumerate(order)}

        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]

            for j in range(len(w1)):
                if j == len(w2):
                    return False

                if w1[j] != w2[j]:
                    if order_index[w1[j]] > order_index[w2[j]]:
                        return False
                    break
        return True

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        int orderIndex[26] = {0};
        for (int i = 0; i < order.size(); ++i)
            orderIndex[order[i] - 'a'] = i;

        for (int i = 0; i < words.size() - 1; ++i) {
            string w1 = words[i], w2 = words[i + 1];
            int j = 0;

            for (; j < w1.size(); ++j) {
                if (j == w2.size()) return false;
                if (w1[j] != w2[j]) {
                    if (orderIndex[w1[j] - 'a'] > orderIndex[w2[j] - 'a'])
                        return false;
                    break;
                }
            }
        }
        return true;
    }
};