Verifying an Alien Dictionary - Practice Coding Problems

Verifying an Alien Dictionary - 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: If the alien alphabet order is "hlabcdefgijkmnopqrstuvwxyz", then "hello" comes before "leetcode" because 'h' < 'l' in this ordering.

Input & Output

Example 1 — Custom Alphabet Order

$ Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"

› Output: true

💡 Note: In the alien alphabet, 'h' comes before 'l', so 'hello' < 'leetcode'. Words are sorted correctly.

Example 2 — Wrong Order

$ Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"

› Output: false

💡 Note: 'word' and 'world' have same prefix 'wor'. Comparing 'd' vs 'l': 'd' comes after 'l' in the order, so 'word' > 'world'. Not sorted.

Example 3 — Prefix Relationship

$ Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"

› Output: false

💡 Note: 'app' is a prefix of 'apple'. Shorter word should come first, but 'apple' comes first here. Not sorted.

Constraints

1 ≤ words.length ≤ 100
1 ≤ words[i].length ≤ 20
order.length == 26
All characters in words[i] and order are English lowercase letters
order contains each letter exactly once

Visualization

Tap to expand

Understanding the Visualization

Input

Words array and custom alphabet order

Process

Compare adjacent words using alien alphabet positions

Output

Return true if words are sorted, false otherwise

Key Takeaway

🎯 Key Insight: Build a position mapping for the alien alphabet to enable fast character comparisons

Asked in

F Facebook 35 G Google 25 a Amazon 15

The key insight is to map each character to its position in the alien alphabet order for fast lookups. Best approach uses hash map for O(1) character position lookup while comparing adjacent word pairs. Time: O(n × m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Character Comparison	O(n × m × k)	O(1)	Compare adjacent words character by character, finding position in order string each time
Hash Map Position Lookup	O(n × m)	O(1)	Build a hash map for O(1) character position lookup, then compare adjacent words

Brute Force Character Comparison — Algorithm Steps

Iterate through adjacent word pairs
Compare each pair character by character
Find character positions in order string for comparison
Return false if any pair is not sorted

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare Words

Compare adjacent words character by character

Find Positions

Look up each character's position in order string

Determine Order

Lower position means earlier in alien alphabet

Code -

solution.c — C

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

int findCharPos(const char* order, char c) {
    for (int i = 0; order[i]; i++) {
        if (order[i] == c) return i;
    }
    return -1;
}

bool compareWords(const char* word1, const char* word2, const char* order) {
    int len1 = strlen(word1), len2 = strlen(word2);
    int minLen = len1 < len2 ? len1 : len2;
    
    for (int i = 0; i < minLen; i++) {
        int pos1 = findCharPos(order, word1[i]);
        int pos2 = findCharPos(order, word2[i]);
        if (pos1 < pos2) return true;
        if (pos1 > pos2) return false;
    }
    return len1 <= len2;
}

bool solution(char words[][100], int wordCount, const char* order) {
    for (int i = 0; i < wordCount - 1; i++) {
        if (!compareWords(words[i], words[i + 1], order)) {
            return false;
        }
    }
    return true;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse words array manually
    char words[100][100];
    int wordCount = 0;
    char* token = strtok(line, "[],\"\n");
    while (token != NULL && strlen(token) > 0) {
        if (token[0] != ' ') {
            strcpy(words[wordCount++], token);
        }
        token = strtok(NULL, "[],\"\n");
    }
    
    char order[27];
    fgets(order, sizeof(order), stdin);
    order[strcspn(order, "\n")] = 0;
    
    bool result = solution(words, wordCount, order);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m × k)

n words, m average length, k=26 to find each character position in order

✓ Linear Growth

Space Complexity

O(1)

Only using variables, no extra data structures

✓ Linear Space

180.0K Views

Medium Frequency

~15 min Avg. Time

2.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Character Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler