953. Verifying an Alien Dictionary - Solution

Q: Is Verifying an Alien Dictionary easy or hard?

LeetCode classifies this problem as Easy. The logic is straightforward once you map the alien alphabet to numeric ranks, but careful handling of prefix cases and character comparisons is required.

Q: Verifying an Alien Dictionary Python/Java solution

Python and Java solutions typically build a dictionary or array mapping each character to its index in the alien order string. Then they iterate through adjacent word pairs and compare characters until a mismatch determines ordering.

Q: How to solve Verifying an Alien Dictionary in O(n*m)?

Create a mapping from each character in the alien order string to its rank. Iterate through each adjacent pair of words and compare characters using that mapping. If the first differing character violates the ranking, return false. Also check the prefix case where a longer word appears before its prefix.

Q: What is the best approach for Verifying an Alien Dictionary?

The most efficient approach maps each character in the alien alphabet to an index and then compares adjacent words character by character. This allows constant-time rank lookups during comparison and verifies ordering in O(n * m) time, where n is the number of words and m is the average word length.

Q: Is Verifying an Alien Dictionary asked at Google/Amazon/Meta?

This problem is commonly used in interviews at companies like Google, Amazon, and Meta because it tests string comparison logic, custom ordering, and careful handling of edge cases such as prefix relationships between words.

Q: What data structure is used in Verifying an Alien Dictionary?

A hash table or fixed-size array is used to map characters to their alien alphabet rank. This enables constant-time lookup when comparing characters between words.

Q: What is the time complexity of Verifying an Alien Dictionary?

The optimal solution runs in O(n * m) time. Each adjacent pair of words is compared character by character until a mismatch occurs. Space complexity is O(1) because the alphabet size is fixed at 26 characters.

The problem

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.

Approach overview

Problem Overview: You receive a list of words and a string describing the alphabet order used by an alien language. Your job is to verify whether the words are sorted according to that custom character order.

The challenge is that the alphabetical order is not the normal English order. You must interpret comparisons between characters using the alien alphabet mapping and check every adjacent pair of words.

Approach 1: Mapping Order Using Indexes (O(n * m) time, O(1) space)

Create a lookup table that maps each character in the alien alphabet to its index (rank). This can be stored in a small array or hash map where order[i] tells you the priority of the character. Then iterate through each adjacent pair of words and compare them character by character. As soon as you find different characters, check their mapped ranks. If the first word has a higher rank character than the second, the list is not sorted.

Handle the prefix edge case carefully. If all characters match up to the shorter word but the first word is longer (for example "apple" before "app"), the order is invalid. The algorithm scans each character once across comparisons, so the total time complexity is O(n * m) where n is the number of words and m is the average word length. The mapping structure uses constant space since the alphabet size is fixed (26).

This approach works well with arrays and simple character indexing. It avoids sorting and focuses only on verifying order.

Approach 2: Using Custom Comparator (O(n * m) time, O(1) space)

Another option is to implement a custom comparator that compares two words using the alien character ranking. First build a character-to-rank map similar to the previous approach. Then define a comparison function that iterates through both strings and decides ordering based on the mapped ranks of the first differing characters.

You can use this comparator either to directly check each adjacent pair or to sort a copy of the list and compare it with the original. If the sorted version matches the original sequence, the dictionary was already correctly ordered. Each comparison scans up to the length of the shorter word, giving O(m) per comparison and O(n * m) overall.

This method mirrors how lexicographic comparison works internally in many languages. It is a clean conceptual solution when working with string comparison logic and custom ordering rules stored in a hash table.

Recommended for interviews: The mapping-order approach is what most interviewers expect. It demonstrates that you understand lexicographic comparison and how to translate a custom alphabet into numeric ranks. The custom comparator approach shows good abstraction skills but still relies on the same core idea of character ranking.

Approach 1: Mapping Order Using Indexes

This approach involves converting each character in the alien order to an index, which can be used to easily compare words. The idea is to take the given order of the language and map each character to its position in the order. Then, we can compare words by comparing their mapped indices.

Python

def isAlienSorted(words: List[str], order: str) -> bool:
    order_idx = {char: idx for idx, char in enumerate(order)}

    def is_in_order(w1, w2):
        length = min(len(w1), len(w2))
        for i in range(length):
            if w1[i] != w2[i]:
                return order_idx[w1[i]] < order_idx[w2[i]]
        return len(w1) <= len(w2)

    for i in range(len(words) - 1):
        if not is_in_order(words[i], words[i + 1]):
            return False
    return True

Java

import java.util.*;

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

        for (int i = 0; i < words.length - 1; i++) {
            if (!inOrder(words[i], words[i + 1], orderIdx)) {
                return false;
            }
        }

        return true;
    }

    private boolean inOrder(String word1, String word2, int[] orderIdx) {
        int minLength = Math.min(word1.length(), word2.length());
        for (int i = 0; i < minLength; i++) {
            if (word1.charAt(i) != word2.charAt(i)) {
                return orderIdx[word1.charAt(i) - 'a'] < orderIdx[word2.charAt(i) - 'a'];
            }
        }
        return word1.length() <= word2.length();
    }
}

C++

#include <string>
#include <vector>
using namespace std;

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

    for (int i = 0; i < words.size() - 1; ++i) {
        const string& w1 = words[i];
        const string& w2 = words[i + 1];
        size_t j = 0;
        while (j < w1.length() && j < w2.length() && w1[j] == w2[j]) {
            ++j;
        }
        if (j < w2.length() && (j >= w1.length() || orderIdx[w1[j] - 'a'] <= orderIdx[w2[j] - 'a'])) continue;
        if (j == w2.length() || orderIdx[w1[j] - 'a'] > orderIdx[w2[j] - 'a']) return false;
    }
    return true;
}

JavaScript

function isAlienSorted(words, order) {
    const orderMap = new Map(order.split('').map((char, idx) => [char, idx]));

    const isInOrder = (word1, word2) => {
        let i = 0;
        while (i < word1.length && i < word2.length) {
            if (word1[i] !== word2[i]) {
                return orderMap.get(word1[i]) < orderMap.get(word2[i]);
            }
            i++;
        }
        return word1.length <= word2.length;
    };

    for (let i = 0; i < words.length - 1; i++) {
        if (!isInOrder(words[i], words[i + 1])) {
            return false;
        }
    }

    return true;
}

#include <stdbool.h>
#include <string.h>

bool isAlienSorted(char ** words, int wordsSize, char * order){
    int orderIdx[26];
    for (int i = 0; i < 26; ++i) {
        orderIdx[order[i] - 'a'] = i;
    }

    for (int i = 0; i < wordsSize - 1; ++i) {
        const char *word1 = words[i];
        const char *word2 = words[i + 1];
        int j = 0;
        while (word1[j] == word2[j] && word1[j] != '\0') {
            j++;
        }
        if (word2[j] == '\0' || (word1[j] != '\0' && orderIdx[word1[j] - 'a'] > orderIdx[word2[j] - 'a'])) {
            return false;
        }
    }

    return true;
}

using System;

public class Solution {
    public bool IsAlienSorted(string[] words, string order) {
        int[] index = new int[26];
        for (int i = 0; i < order.Length; i++) {
            index[order[i] - 'a'] = i;
        }
        for (int i = 0; i < words.Length - 1; i++) {
            if (!InOrder(words[i], words[i+1], index)) {
                return false;
            }
        }
        return true;
    }

    private bool InOrder(string word1, string word2, int[] index) {
        int minLength = Math.Min(word1.Length, word2.Length);
        for (int i = 0; i < minLength; i++) {
            if (word1[i] != word2[i]) {
                return index[word1[i] - 'a'] < index[word2[i] - 'a'];
            }
        }
        return word1.Length <= word2.Length;
    }
}

In Python, we create a dictionary to store the order of each character. We define an is_in_order function to check if two words are in the required order based on the alien dictionary. We iterate over word pairs and return false if any are out of order.

Complexity

Time Complexity: O(N), where N is the total number of characters. Space Complexity: O(1) for mapping, ignoring input storage.

Try this approach in the editor

Approach 2: Using Custom Comparator

This approach employs a custom comparator to sort the words based on the alien order. We first map the order and then define a comparator that sorts based on this map. We check if the sorted version of the words matches the original order, indicating that they were sorted correctly in the alien dictionary.

Python

def isAlienSorted(words: List[str], order: str) -> bool:
    order_idx = {char: idx for idx, char in enumerate(order)}

    sorted_words = sorted(words, key=lambda word: [order_idx[char] for char in word])
    return sorted_words == words

Java

import java.util.*;

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

        String[] sortedWords = words.clone();
        Arrays.sort(sortedWords, (w1, w2) -> {
            int minLength = Math.min(w1.length(), w2.length());
            for (int i = 0; i < minLength; i++) {
                if (w1.charAt(i) != w2.charAt(i)) {
                    return orderIdx[w1.charAt(i) - 'a'] - orderIdx[w2.charAt(i) - 'a'];
                }
            }
            return w1.length() - w2.length();
        });

        return Arrays.equals(words, sortedWords);
    }
}

C++

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

vector<int> orderIdx;

bool customComparator(const string &w1, const string &w2) {
    size_t minLen = min(w1.size(), w2.size());
    for (size_t i = 0; i < minLen; ++i) {
        if (w1[i] != w2[i]) {
            return orderIdx[w1[i] - 'a'] < orderIdx[w2[i] - 'a'];
        }
    }
    return w1.size() < w2.size();
}

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

    vector<string> sortedWords = words;
    sort(sortedWords.begin(), sortedWords.end(), customComparator);

    return sortedWords == words;
}

JavaScript

function isAlienSorted(words, order) {
    const orderMap = new Map(order.split('').map((char, idx) => [char, idx]));

    const sortedWords = [...words].sort((a, b) => {
        let i = 0;
        while (i < a.length && i < b.length) {
            if (a[i] !== b[i]) {
                return orderMap.get(a[i]) - orderMap.get(b[i]);
            }
            i++;
        }
        return a.length - b.length;
    });

    return sortedWords.every((word, index) => word === words[index]);
}

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

int orderIdx[26];

int comp(const void *a, const void *b) {
    const char *word1 = *(const char **)a;
    const char *word2 = *(const char **)b;
    int i = 0;
    while (word1[i] != '\0' && word2[i] != '\0' && word1[i] == word2[i]) {
        i++;
    }
    if (word1[i] == '\0' || word2[i] == '\0') {
        return strlen(word1) - strlen(word2);
    }
    return orderIdx[word1[i] - 'a'] - orderIdx[word2[i] - 'a'];
}

bool isAlienSorted(char ** words, int wordsSize, char * order) {
    for (int i = 0; i < 26; i++) {
        orderIdx[order[i] - 'a'] = i;
    }

    for (int i = 0; i < wordsSize - 1; i++) {
        if (comp(&words[i], &words[i+1]) > 0) {
            return false;
        }
    }

    return true;
}

using System;
using System.Collections.Generic;

public class Solution {
    public bool IsAlienSorted(string[] words, string order) {
        int[] index = new int[26];
        for (int i = 0; i < order.Length; i++) {
            index[order[i] - 'a'] = i;
        }

        List<string> sortedWords = new List<string>(words);
        sortedWords.Sort((w1, w2) => {
            int minLength = Math.Min(w1.Length, w2.Length);
            for (int i = 0; i < minLength; i++) {
                if (w1[i] != w2[i]) {
                    return index[w1[i] - 'a'] - index[w2[i] - 'a'];
                }
            }
            return w1.Length - w2.Length;
        });

        for (int i = 0; i < words.Length; i++) {
            if (!words[i].Equals(sortedWords[i])) return false;
        }
        return true;
    }
}

In Python, we use the sorted function with a lambda function to sort words based on the alien dictionary order. Then we check if the sorted version matches the input.

Complexity

Time Complexity: O(N log N). Space Complexity: O(N) due to sorting operations.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function isAlienSorted(words: string[], order: string): boolean {
    const map = new Map();
    for (const c of order) {
        map.set(c, map.size);
    }
    const n = words.length;
    for (let i = 1; i < n; i++) {
        const s1 = words[i - 1];
        const s2 = words[i];
        const m = Math.min(s1.length, s2.length);
        let isEqual = false;
        for (let j = 0; j < m; j++) {
            if (map.get(s1[j]) > map.get(s2[j])) {
                return false;
            }
            if (map.get(s1[j]) < map.get(s2[j])) {
                isEqual = true;
                break;
            }
        }
        if (!isEqual && s1.length > s2.length) {
            return false;
        }
    }
    return true;
}

func isAlienSorted(words []string, order string) bool {
	m := make([]int, 26)
	for i, c := range order {
		m[c-'a'] = i
	}
	for i := 0; i < 20; i++ {
		prev := -1
		valid := true
		for _, x := range words {
			curr := -1
			if i < len(x) {
				curr = m[x[i]-'a']
			}
			if prev > curr {
				return false
			}
			if prev == curr {
				valid = false
			}
			prev = curr
		}
		if valid {
			break
		}
	}
	return true
}

Rust

use std::collections::HashMap;
impl Solution {
    pub fn is_alien_sorted(words: Vec<String>, order: String) -> bool {
        let n = words.len();
        let mut map = HashMap::new();
        order.as_bytes().iter().enumerate().for_each(|(i, &v)| {
            map.insert(v, i);
        });
        for i in 1..n {
            let s1 = words[i - 1].as_bytes();
            let s2 = words[i].as_bytes();
            let mut is_equal = true;
            for i in 0..s1.len().min(s2.len()) {
                if map.get(&s1[i]) > map.get(&s2[i]) {
                    return false;
                }
                if map.get(&s1[i]) < map.get(&s2[i]) {
                    is_equal = false;
                    break;
                }
            }
            if is_equal && s1.len() > s2.len() {
                return false;
            }
        }
        true
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Mapping Order Using Indexes	Time Complexity: `O(N)`, where `N` is the total number of characters. Space Complexity: `O(1)` for mapping, ignoring input storage.
Using Custom Comparator	Time Complexity: `O(N log N)`. Space Complexity: `O(N)` due to sorting operations.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Mapping Order Using Indexes	O(n * m)	O(1)	Best general solution. Efficiently compares adjacent words using precomputed character ranks.
Custom Comparator	O(n * m)	O(1)	Useful when implementing language-style string comparison or sorting with custom ordering.

Frequently asked questions

Is Verifying an Alien Dictionary easy or hard?

LeetCode classifies this problem as Easy. The logic is straightforward once you map the alien alphabet to numeric ranks, but careful handling of prefix cases and character comparisons is required.

Verifying an Alien Dictionary Python/Java solution

Python and Java solutions typically build a dictionary or array mapping each character to its index in the alien order string. Then they iterate through adjacent word pairs and compare characters until a mismatch determines ordering.

How to solve Verifying an Alien Dictionary in O(n*m)?

Create a mapping from each character in the alien order string to its rank. Iterate through each adjacent pair of words and compare characters using that mapping. If the first differing character violates the ranking, return false. Also check the prefix case where a longer word appears before its prefix.

What is the best approach for Verifying an Alien Dictionary?

The most efficient approach maps each character in the alien alphabet to an index and then compares adjacent words character by character. This allows constant-time rank lookups during comparison and verifies ordering in O(n * m) time, where n is the number of words and m is the average word length.

Is Verifying an Alien Dictionary asked at Google/Amazon/Meta?

This problem is commonly used in interviews at companies like Google, Amazon, and Meta because it tests string comparison logic, custom ordering, and careful handling of edge cases such as prefix relationships between words.

What data structure is used in Verifying an Alien Dictionary?

A hash table or fixed-size array is used to map characters to their alien alphabet rank. This enables constant-time lookup when comparing characters between words.

What is the time complexity of Verifying an Alien Dictionary?

The optimal solution runs in O(n * m) time. Each adjacent pair of words is compared character by character until a mismatch occurs. Space complexity is O(1) because the alphabet size is fixed at 26 characters.

Verifying an Alien Dictionary solution and explanation

The problem

Approach overview

Approach 1: Mapping Order Using Indexes

Approach 2: Using Custom Comparator

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Verifying an Alien Dictionary solution and explanation

The problem

Approach overview

Approach 1: Mapping Order Using Indexes

Approach 2: Using Custom Comparator

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems