# 👽 Verifying an Alien Dictionary (LeetCode 953)

Imagine you're interviewing on another planet. 🌎➡️🛸

The aliens use the same English lowercase letters (a-z), but their alphabet order is completely different!

Your task is to determine whether a list of words is sorted according to the alien alphabet.

---

📌 Problem Statement

Given:

• An array of words
• A string representing the alien alphabet order

Return:

• true if the words are sorted lexicographically according to the alien language
• false otherwise

---

🧠 Example 1

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

Output:

true

Why?

The first differing characters are:

hello
leetcode
↑
h comes before l

Since h < l in the alien language, the words are correctly ordered.

---

🧠 Example 2

words = ["word","world","row"]
order = "worldabcefghijkmnpqstuvxyz"

Output:

false

Comparison:

word
world

First differing characters:

word
worl(d)
    ↑

world
worl(l)
    ↑

In the alien dictionary, d appears after l, making:

word > world

which violates the sorted order.

---

🧠 Example 3

words = ["apple","app"]
order = "abcdefghijklmnopqrstuvwxyz"

Output:

false

Both words share the prefix:

app

But:

apple
app

The shorter word should come first.

Just like:

app < apple

Therefore:

apple > app

and the list is not sorted.

---

🔍 Key Observation

Comparing words in an alien language is exactly like comparing words in English.

The only difference is:

Character ranking is different.

So instead of comparing characters directly:

'a' < 'b'

we compare their positions in the alien alphabet.

---

🚀 Step 1: Build Character Ranking

Given:

order = "hlabcdefgijkmnopqrstuvwxyz"

Create a mapping:

h → 0
l → 1
a → 2
b → 3
...

This allows us to instantly know which character comes first.

---

🚀 Step 2: Compare Adjacent Words

If the entire list is sorted, then every adjacent pair must also be sorted.

So compare:

words[0] vs words[1]
words[1] vs words[2]
words[2] vs words[3]
...

If any comparison fails, return false.

---

🚀 Step 3: Compare Two Words

Consider:

hello
leetcode

Compare character by character:

h vs l

As soon as characters differ:

• If first character comes before second → valid
• Otherwise → invalid

No need to check the remaining characters.

---

⚠️ Special Case: Prefix Problem

Consider:

apple
app

All common characters match:

app
app

Now one word ends.

Lexicographical rule:

Shorter word comes first.

Therefore:

app < apple

If the first word is longer:

apple > app

Return false.

---

✅ Java Solution

class Solution {
    public boolean isAlienSorted(String[] words, String order) {
        int n = words.length;

        int[] charToIdxMap = new int[26];
        for(int i = 0; i < 26; i++) {
            charToIdxMap[order.charAt(i) - 'a'] = i;
        }

        for(int i = 1; i < n; i++) {
            if(!isValid(words[i - 1], words[i], charToIdxMap)) {
                return false;
            }
        }

        return true;
    }

    public boolean isValid(String word0, String word1, int[] charToIdxMap) {
        int n0 = word0.length();
        int n1 = word1.length();
        int len = Math.min(n0, n1);

        for(int i = 0; i < len; i++) {
            char ch1 = word0.charAt(i);
            char ch2 = word1.charAt(i);

            if(ch1 != ch2) {
                return charToIdxMap[ch1 - 'a'] < charToIdxMap[ch2 - 'a'];
            }
        }

        return n0 <= n1;
    }
}

---

🎯 Dry Run

Input:

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

Build Mapping

h → 0
l → 1
a → 2
...

---

Compare

hello
leetcode

First characters:

h vs l

Mapped positions:

h → 0
l → 1

Since:

0 < 1

the pair is valid.

No more pairs remain.

Return:

true

---

⏱️ Time Complexity

Let:

• N = number of words
• L = average word length

Building the map:

O(26)

Comparing adjacent words:

O(N × L)

Overall:

Time Complexity = O(N × L)

---

💾 Space Complexity

We store the character ranking map:

int[26]

Therefore:

Space Complexity = O(1)

because the alphabet size is fixed.

---

🔥 Interview Takeaways

This problem tests:

• Custom sorting logic
• Lexicographical comparison
• String processing
• Edge cases involving prefixes
• Efficient use of character mappings

The most important insight is:

Don't compare characters directly. Compare their positions in the alien alphabet.

Once you build the ranking map, the rest becomes a straightforward lexicographical comparison problem.

---

💬 What do you think?

Have you seen a variation of this problem where the alien alphabet order was not given directly but had to be derived from the words themselves? That's an interesting follow-up often asked in interviews. Let me know how you would approach it! 👇