Verifying an Alien Dictionary

Easy Top 250

Associated Patterns

Interviewed At (Company Tags)

AmazonGoogleMetaApple

Problem Description

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 English letters.

Given a list 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.

Examples

Example 1:

Input: words = [“hello”,“leetcode”], order = “hlabcdefgijkmnopqrstuvwxyz” Output: true

Example 2:

Input: words = [“word”,“world”,“row”], order = “worldabcefghijkmnpqstuvxyz” Output: false

Example 3:

Input: words = [“apple”,“app”], order = “abcdefghijklmnopqrstuvwxyz” Output: false Explanation: “apple” comes before “app” but has more characters, so this ordering is wrong.

Constraints

1 ≤ words.length ≤ 100
1 ≤ words[i].length ≤ 20
order.length == 26

Map Order, Then Compare Adjacent Words

Build a rank array: rank[c] = position in alien order for each character. Then compare each adjacent pair of words character by character. The first differing character determines the ordering. If no character differs and one word is a prefix of the other, the shorter one must come first.

Solution

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int[] rank = new int[26];
        for (int i = 0; i < 26; i++) rank[order.charAt(i) - 'a'] = i;

        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i], w2 = words[i + 1];
            boolean found = false;
            for (int j = 0; j < Math.min(w1.length(), w2.length()); j++) {
                int r1 = rank[w1.charAt(j) - 'a'], r2 = rank[w2.charAt(j) - 'a'];
                if (r1 < r2) { found = true; break; }
                if (r1 > r2) return false; // wrong order
            }
            // if no differing char found, longer word must not come first
            if (!found && w1.length() > w2.length()) return false;
        }
        return true;
    }
}

class Solution:
    def isAlienSorted(self, words: list[str], order: str) -> bool:
        rank = {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(min(len(w1), len(w2))):
                if rank[w1[j]] < rank[w2[j]]:
                    break  # correct order found
                if rank[w1[j]] > rank[w2[j]]:
                    return False  # wrong order
            else:
                # no differing char: w1 must not be longer
                if len(w1) > len(w2):
                    return False

        return True

#include <vector>
#include <string>

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

        for (int i = 0; i < (int)words.size() - 1; i++) {
            const std::string& w1 = words[i], &w2 = words[i + 1];
            bool found = false;
            for (int j = 0; j < (int)std::min(w1.size(), w2.size()); j++) {
                if (rank[w1[j] - 'a'] < rank[w2[j] - 'a']) { found = true; break; }
                if (rank[w1[j] - 'a'] > rank[w2[j] - 'a']) return false;
            }
            if (!found && w1.size() > w2.size()) return false;
        }
        return true;
    }
};

Complexity Analysis:

Time Complexity: O(C) where C is total number of characters across all words. Each character is compared at most once.
Space Complexity: O(1). The rank array has fixed size 26.

Where it breaks: the prefix check (w1.length() > w2.length() when no differing character found) is the tricky edge case. "apple" then "app" looks valid character-by-character until you run out of "app", but since "apple" is longer and comes first, it’s invalid.