Verifying an Alien Dictionary

78.1k
0

Given an array words containing lowercase English words and a string order representing a permutation of all 26 lowercase English letters, return true when words is sorted lexicographically according to the alien alphabet.

Return false when any word appears before another word that should come earlier according to order..

Example 1

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

Output: true

Explanation: The first characters differ. Character 'h' appears before 'l' in the alien alphabet, so "hello" correctly appears before "leetcode".

Example 2

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

Output: false

Explanation: Words "word" and "world" match for the first three characters. The first mismatch contains 'd' in "word" and 'l' in "world". Character 'l' appears before 'd' in the alien alphabet, so "world" should appear before "word".

Example 3

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

Output: false

Explanation: Word "app" is an exact prefix of "apple". Lexicographic order requires the shorter word to appear first, but "apple" appears before "app".

Brute Force Approach

A correctly sorted sequence remains unchanged after sorting under the same ordering rules. Rebuilding the expected alien-sorted sequence and comparing the result with the original sequence therefore provides a direct verification method.

Normal character comparison cannot be used because the alien alphabet may assign different priorities. A rank lookup converts every alien character into a numerical position. A custom comparator then uses the first mismatching character to decide word order. When one word is an exact prefix of another, the shorter word receives the smaller position.

Algorithm

  • Initialize a rank array of size 26 to store the position of every lowercase character inside order.

  • Traverse order and store the rank of each character using the character offset from 'a'.

  • Create sortedWords as a copy of words, preserving the original sequence for final comparison.

  • Sort sortedWords using a custom alien-language comparator.

  • Compare two words character by character until the first mismatch appears.

  • Place the word containing the lower-ranked mismatching character first.

  • Place the shorter word first when all characters match up to the end of the shorter word.

  • Compare sortedWords with words.

  • Return true when both sequences match completely; otherwise, return false.

Dry Run

f

f

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
array<int, 26> rank{};
/* Compares two words using alien character ranks. */
bool comesBefore(
const string& first,
const string& second
) {
int commonLength = min(
first.length(),
second.length()
);
// Use the first mismatching character.
for (
int index = 0;
index < commonLength;
index++
) {
if (first[index] != second[index]) {
return rank[first[index] - 'a'] <
rank[second[index] - 'a'];
}
}
// Place the shorter word first for a prefix match.
return first.length() < second.length();
}
public:
/* Verifies order by sorting a copied word list. */
bool isAlienSorted(
vector<string>& words,
string order
) {
// Store the rank of every alien character.
for (int index = 0; index < 26; index++) {
rank[order[index] - 'a'] = index;
}
// Preserve the original sequence for comparison.
vector<string> sortedWords = words;
// Rebuild the expected alien-sorted sequence.
sort(
sortedWords.begin(),
sortedWords.end(),
[&](const string& first,
const string& second) {
return comesBefore(first, second);
}
);
return sortedWords == words;
}
};
// Driver code to execute the solution.
int main() {
vector<string> words = {
"hello",
"leetcode"
};
string order =
"hlabcdefgijkmnopqrstuvwxyz";
Solution solution;
bool answer =
solution.isAlienSorted(words, order);
cout << boolalpha << answer << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log N × M), where N represents the number of words and M represents the maximum word length. Sorting performs O(N log N) comparisons, and a comparison can inspect up to M characters.

Space Complexity: O(N × M) in the C++ value-copy implementation because sortedWords duplicates the stored string contents. Python, Java, and JavaScript copy the outer sequence or string references, requiring O(N) container space, excluding sorting internals. The rank array requires O(26), simplified to O(1).

Better Approach

Sorting the complete array performs more work than verification requires. A sequence is sorted when every adjacent pair follows the required order. Therefore, checking (words[0], words[1]), then (words[1], words[2]), and continuing through the array is sufficient.

A Hash Map stores the alien rank of every character. For each adjacent pair, the first mismatching character decides the order. When no mismatch appears, only the prefix rule remains relevant. Any invalid pair proves that the complete sequence is unsorted, allowing immediate termination.

Algorithm

  • Initialize an empty Hash Map rank to associate every alien character with the corresponding priority.

  • Traverse order and store each character with the current index.

  • Traverse adjacent word pairs from index 0 to N - 2.

  • Select first = words[i] and second = words[i + 1].

  • Compare both words from left to right up to the length of the shorter word.

  • Stop at the first mismatching character because later characters cannot affect lexicographic order.

  • Return false when the character from first has a greater alien rank than the character from second.

  • Mark the pair as valid when the character from first has a smaller rank.

  • Check the prefix condition when no mismatch appears.

  • Return false when first is longer than second, because a longer word cannot appear before an exact prefix.

  • Return true after every adjacent pair satisfies the alien ordering rules.

Dry Run

f

f

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/* Checks one adjacent pair with Hash Map ranks. */
bool inCorrectOrder(
const string& first,
const string& second,
const unordered_map<char, int>& rank
) {
int commonLength = min(
first.length(),
second.length()
);
// Use the first mismatching character.
for (
int index = 0;
index < commonLength;
index++
) {
if (first[index] != second[index]) {
return rank.at(first[index]) <
rank.at(second[index]);
}
}
// Reject a longer word before its exact prefix.
return first.length() <= second.length();
}
public:
/* Verifies adjacent pairs with Hash Map ranks. */
bool isAlienSorted(
vector<string>& words,
string order
) {
unordered_map<char, int> rank;
// Map every character to the alien rank.
for (int index = 0; index < 26; index++) {
rank[order[index]] = index;
}
// A sorted sequence needs every pair valid.
for (
int index = 0;
index + 1 < (int)words.size();
index++
) {
if (!inCorrectOrder(
words[index],
words[index + 1],
rank
)) {
return false;
}
}
return true;
}
};
// Driver code to execute the solution.
int main() {
vector<string> words = {
"hello",
"leetcode"
};
string order =
"hlabcdefgijkmnopqrstuvwxyz";
Solution solution;
bool answer =
solution.isAlienSorted(words, order);
cout << boolalpha << answer << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × M), where N represents the number of words and M represents the maximum word length. At most N - 1 adjacent pairs are processed, and each pair can require up to M character comparisons.

Space Complexity: O(26), simplified to O(1), because the Hash Map stores ranks for exactly 26 lowercase English letters.

Optimal Approach

The Better Approach already removes sorting and checks every adjacent pair only once. However, a Hash Map is unnecessary for a fixed alphabet containing exactly 26 lowercase English letters.

A fixed integer array can store every character rank directly. Character 'a' maps to index 0, character 'b' maps to index 1, and so on. Direct array access removes hashing and collision-management overhead while preserving the same adjacent-comparison logic.

The asymptotic complexity remains unchanged. The improvement comes from simpler storage and faster constant-time rank access.

Algorithm

  • Initialize an integer array rank of size 26.

  • Traverse order and store each alien rank using rank[order[i] - 'a'] = i.

  • Traverse every adjacent pair of words.

  • Compare corresponding characters from left to right.

  • Retrieve character priorities directly through the rank array.

  • Return false when the first mismatching character in the first word has a greater rank.

  • Stop comparing the current pair when the first word has a smaller mismatching rank, because the pair is already valid.

  • Check the prefix condition when all compared characters match.

  • Return false when the first word is longer than the second word.

  • Return true after every adjacent pair remains valid.

Dry Run

fa

fa

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/* Checks one adjacent pair with direct lookup. */
bool inCorrectOrder(
const string& first,
const string& second,
const array<int, 26>& rank
) {
int commonLength = min(
first.length(),
second.length()
);
// Use the first mismatching character.
for (
int index = 0;
index < commonLength;
index++
) {
if (first[index] != second[index]) {
return rank[first[index] - 'a'] <
rank[second[index] - 'a'];
}
}
// Reject a longer word before its exact prefix.
return first.length() <= second.length();
}
public:
/* Verifies adjacent pairs with a rank array. */
bool isAlienSorted(
vector<string>& words,
string order
) {
array<int, 26> rank{};
// Store each rank by character offset.
for (int index = 0; index < 26; index++) {
rank[order[index] - 'a'] = index;
}
// A sorted sequence needs every pair valid.
for (
int index = 0;
index + 1 < (int)words.size();
index++
) {
if (!inCorrectOrder(
words[index],
words[index + 1],
rank
)) {
return false;
}
}
return true;
}
};
// Driver code to execute the solution.
int main() {
vector<string> words = {
"hello",
"leetcode"
};
string order =
"hlabcdefgijkmnopqrstuvwxyz";
Solution solution;
bool answer =
solution.isAlienSorted(words, order);
cout << boolalpha << answer << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × M), where N represents the number of words and M represents the maximum word length. Every adjacent pair is processed once, and a pair can require up to M character comparisons.

Space Complexity: O(26), simplified to O(1), because the rank array always contains exactly 26 entries.

FAQs about Verifying an Alien Dictionary

1. Why does only the first mismatching character matter?

Lexicographic comparison ends at the first unequal character. The lower-ranked character determines which word must appear first, so later characters cannot change the result.

2. Why must a shorter prefix appear before a longer word?

No mismatching character exists when one word is an exact prefix. Length becomes the deciding condition, and the shorter word receives the earlier lexicographic position.

For example, "app" must appear before "apple".

3. Are two identical adjacent words considered correctly sorted?

Yes. Every compared character matches, and both lengths are equal. Equal values are valid inside a non-decreasing sorted sequence.

4. Why are adjacent comparisons sufficient?

For a sorted sequence:

word[0] <= word[1] <= word[2] <= ...

Every adjacent relation must hold. One invalid adjacent pair breaks the complete ordering.

5. Does the fixed-array approach improve the asymptotic complexity?

No. Both adjacent-comparison approaches require O(N × M) time and O(1) auxiliary space. The array removes Hash Map overhead and improves constant factors.

6. Why is sorting a copied array slower?

Sorting requires O(N log N) word comparisons, while adjacent verification requires only N - 1 word comparisons.

7. What happens when the array contains zero or one word?

The sequence is already sorted because no adjacent pair can violate the ordering. Every implementation returns true.

8. Does the solution need to validate the order string?

No additional validation is required when the problem guarantees that order contains every lowercase English letter exactly once.

9. Can uppercase letters be handled by the same rank array?

The current array contains only 26 lowercase-letter positions. A larger rank structure or a Hash Map would be required for uppercase letters or a broader character set.

ArraysStringHashing

Read Similar Blogs

HashingData Structures

Count Distinct Elements

Given an integer array arr[] , return the count of all distinct elements in the array. Input: arr = [10, 20, 20, 10, 30, 10] Output: 3 Explanation: The different values are 10 , 20 , and 30 . 10 an...

76.4k
Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0...

67.1k
Comments0