953. Verifying an Alien Dictionary
Problem Description
In the given problem, we're dealing with a hypothetical alien language that uses the same lowercase letters as English but has a different ordering of these letters. This order is represented by the string order
, where each character's position indicates its rank in the alien alphabetical order.
We're given a list of words called words
, which are supposedly written in this alien language. Our task is to determine if these words are sorted according to the alien lexicographical order. To put it simply, we need to confirm if each word would appear before the following word in a dictionary organized by the provided alien alphabet.
The lexicographical order is similar to what we're familiar with in an English dictionary—'apple' comes before 'banana' because 'a' is before 'b' in the English alphabetical order. However, for this problem, we need to ignore the English alphabetical order and instead use the provided order
string to determine the sorting sequence.
To solve this, we have to read the words list using the alien alphabet and confirm that each subsequent word is either the same up to a point and then greater according to the alien alphabet, or entirely greater if compared at the same position in each word.
In essence, we need to write a function that checks this sorting without reordering the list—a simple 'yes' or 'no' to whether the list is already sorted as per the alien dictionary.
Intuition
The intuition behind the provided solution approach is to use a dictionary named m
to represent the mapping of each character in the alien language to its corresponding index according to order
. Once we have this mapping, it is much easier to compare the words.
During the comparison, we want to ensure that for each position i
up to the length of the longest word (in this case, arbitrarily chosen as 20, assuming no word is longer than 20 characters), the following holds true:
-
If the character at position
i
in the previous word has a higher index in our alien dictionary than the character at positioni
in the current word, we should immediately returnFalse
, as this indicates that the list is not sorted. -
If characters at position
i
are the same, we continue our checks without concluding anything just yet because the subsequent characters might determine the order. -
If at this position
i
, we do not encounter any characters that are out of order, and all comparisons were either equal or in sorted order, we can returnTrue
as this means the list is sorted correctly up to this character. -
If after checking all positions
i
, we haven't returnedFalse
, it is safe to assume that the list is sorted according to the alien language, and we returnTrue
.
The code smartly exits early when it finds evidence the words are not in order, and avoids unnecessary comparisons for characters beyond the length of the shortest word, due to the handling of current and previous character index (curr
and prev
) with default values ensuring proper comparison even if one of the words is shorter.
Solution Approach
The solution provided makes use of a hash table (or dictionary in Python) and single-pass comparisons to implement the algorithm.
Here's a step-by-step breakdown of the implementation:
-
Mapping the Order: We start by creating a dictionary
m
where the key is each character of the alien alphabet and the value is its position in theorder
string. This mapping allows us to efficiently translate each character in the alien words into its corresponding rank in the alien language.m = {c: i for i, c in enumerate(order)}
Using
enumerate
, each characterc
is paired with its indexi
, effectively creating a rank ordering for the alien alphabet. -
Comparing Characters in Words: The code uses a
for
loop to iterate over the positions of the characters in the words, up to a predefined limit of 20 (assuming that none of the words will be longer than that). For each positioni
, it compares characters from different words at the same index.for i in range(20): # ...
-
Tracking and Comparing Ranks of Characters: Inside the loop, two variables
prev
andcurr
are used to track the rank of the current and previous characters, respectively. Initially,prev
is set to -1 to ensure that the first comparison is valid.prev = -1
-
Checking Sorted Order: As we iterate over each word
x
inwords
, we check if the current character's rank is less than the previous one. Since we are performing lexicographical comparison, any current character (curr
) with a lower rank than previous (prev
) would mean the list is not sorted.curr = -1 if i >= len(x) else m[x[i]] if prev > curr: return False
-
Validating Sequential Characters: If the previous character is the same as the current one,
valid
is set toFalse
.valid
is used to track whether all characters compared up to that point have been the same, in which case we need to check further.if prev == curr: valid = False
-
Early Termination: If at any point, we successfully pass through all the words and their characters at a certain index without returning
False
, andvalid
remainsTrue
, it means we found a lexicographical order and can returnTrue
immediately. Otherwise, we continue.if valid: return True
-
Final Verdict: If we reach the end of our positional checks (the
for
loop) without finding any characters out of order, we conclude that the words list is sorted according to the alien dictionary.return True
Key algorithms and data structures used in this implementation include the hash table for constant-time look-up, and a comparison framework that examines each word character-by-character using its index. The process of early termination after successful sequential checks leverages a common pattern in sorting algorithms to optimize performance by avoiding unnecessary work.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach. Imagine we are given the following alien order and a list of words:
order = "hlabcdefgijkmnopqrstuvwxyz" words = ["hello", "leetcode"]
We will walk through checking if the words are sorted according to this alien language.
-
Mapping the Order:
- Using the provided
order
, we create a mappingm
that will let us compare the characters based on their alien language order. - The mapping would result in:
{'h': 0, 'l': 1, 'a': 2, ... 'z': 25}
.
- Using the provided
-
Comparing Characters in Words:
- We set up a loop that will go up to 20, which is more than enough for our example.
-
Tracking and Comparing Ranks of Characters:
- We initialize
prev = -1
to indicate the start of comparisons. - We will compare the ranks of characters at each position within the words.
- We initialize
-
Checking Sorted Order:
- Starting with "hello", we get the rank of 'h' as 0 for position 0. There's no previous word, so we move on.
- Next is "leetcode":
- We compare 'l' (at position 0) of "leetcode" with 'h' of "hello".
- In the mapping
m
, 'l' has a rank of 1 and 'h' has a rank of 0. Since 1 is greater than 0, the order is maintained.
- Continue the loop until either the words are found to be in disorder or all characters are successfully compared.
-
Validating Sequential Characters:
- When comparing characters at the same position, if they are equal, we proceed with further positions as we need more characters to determine the order.
- If all characters are equal up to the minimum length of the two words, we also proceed to the next word in the list.
-
Early Termination:
- In our example, if we found 'g' in "hello" greater than 'e' in "leetcode" at any given position, we would terminate and return
False
. - However, since 'h' is less than 'l' at the first position and there are no other characters in disorder, we do not terminate early and continue.
- In our example, if we found 'g' in "hello" greater than 'e' in "leetcode" at any given position, we would terminate and return
-
Final Verdict:
- After checking all positions and finding no disorder, we return
True
, meaning the list is sorted according to the alien dictionary.
- After checking all positions and finding no disorder, we return
In practice, the comparison process stops at the first instance where prev > curr
. As "hello" and "leetcode" are in correct order in this alien language (since 'h' < 'l'), the result of our checks would be True
. The words are indeed sorted according to the alien alphabet given.
Solution Implementation
1class Solution:
2 def isAlienSorted(self, words: List[str], order: str) -> bool:
3 # Create a mapping from each alien character to its order index for easy comparison.
4 order_index = {char: index for index, char in enumerate(order)}
5
6 # Iterate up to 20 characters, assuming no word is longer than 20 characters.
7 for i in range(20):
8 previous_index = -1 # Start with a comparison index of -1 for the first character.
9 is_sorted_until_now = True # Flag to keep track of whether the order is sorted up to the current character index.
10
11 # Go through all the words to compare the characters at the current index i.
12 for word in words:
13 # If the current index is greater than the word length, use a default index of -1.
14 # Else, use the mapped order index of the current character.
15 current_index = -1 if i >= len(word) else order_index[word[i]]
16
17 # If the previous character's index is greater than the current character's index, the list is not sorted.
18 if previous_index > current_index:
19 return False
20
21 # If the previous character's index is the same as the current, we can't be sure if it is sorted and need to check the next character.
22 if previous_index == current_index:
23 is_sorted_until_now = False
24
25 # Update the previous_index to the current character's order index for the next iteration.
26 previous_index = current_index
27
28 # If all words are sorted until now, no need to check further characters.
29 if is_sorted_until_now:
30 return True
31
32 # If no problems were found in the above loop, the words list is sorted according to the alien language.
33 return True
34
1class Solution {
2
3 // Method to check if the words are sorted as per the given alien dictionary order
4 public boolean isAlienSorted(String[] words, String order) {
5 // Mapping from character to its position in the alien language
6 int[] charIndexMapping = new int[26];
7 for (int i = 0; i < order.length(); ++i) {
8 // Subtract 'a' to convert char into an index (0-25), then assign its order
9 charIndexMapping[order.charAt(i) - 'a'] = i;
10 }
11
12 searchLoop:
13 for (int i = 0; i < 20; ++i) { // Iterate at most up to 20 times, the maximum word length
14 int previousIndex = -1; // Initialize previous character index as -1
15 boolean isDistinct = true; // Flag to check if all chars at position i were unique so far
16
17 // Iterate over words to compare characters at index i
18 for (String word : words) {
19 // If i is greater than word length, currIndex is -1; else, get char's alien order index
20 int currentIndex = i >= word.length() ? -1 : charIndexMapping[word.charAt(i) - 'a'];
21
22 // If previous index is greater than the current index, words are not sorted
23 if (previousIndex > currentIndex) {
24 return false;
25 }
26
27 // If previous index is equal to the current index, we can't confirm order; isDistinct is false
28 if (previousIndex == currentIndex) {
29 isDistinct = false;
30 }
31
32 previousIndex = currentIndex; // Update previousIndex for next iteration
33 }
34
35 // If all words had distinct characters or reached the end, exit from the loop
36 if (isDistinct) {
37 break searchLoop;
38 }
39 }
40
41 return true; // Return true if words are sorted as per alien language
42 }
43}
44
1class Solution {
2public:
3 // Function to check if the words vector is sorted according to the provided alien dictionary order.
4 bool isAlienSorted(vector<string>& words, string order) {
5 // Create a mapping from character to its index in the alien language
6 vector<int> charIndexMap(26);
7 for (int i = 0; i < 26; ++i) {
8 // order[i] - 'a' calculates the offset index from 'a' for the character in the alien language
9 charIndexMap[order[i] - 'a'] = i;
10 }
11
12 // Compare each word with the next one to see if they are in the correct order
13 for (auto it = words.begin(); it != prev(words.end()); ++it) {
14 // If the current word is greater than the next word, return false
15 if (!isCorrectOrder(*it, *next(it), charIndexMap)) {
16 return false;
17 }
18 }
19
20 // If all the words are in the correct order, return true
21 return true;
22 }
23
24private:
25 // Helper function to determine if two words are in the correct order according to the alien dictionary.
26 bool isCorrectOrder(const string &word1, const string &word2, const vector<int>& charIndexMap) {
27 int len1 = word1.size(), len2 = word2.size();
28 for (int i = 0; i < min(len1, len2); ++i) {
29 // Compare character by character according to the alien dictionary order
30 int char1Index = charIndexMap[word1[i] - 'a'];
31 int char2Index = charIndexMap[word2[i] - 'a'];
32
33 // If characters are different and correctly ordered, word1 is less than word2, stop comparing
34 if (char1Index < char2Index) return true;
35
36 // If characters are not in the correct order, return false
37 if (char1Index > char2Index) return false;
38 }
39
40 // If words are equal for min(len1, len2), the shorter word should come first
41 return len1 <= len2;
42 }
43};
44
1function isAlienSorted(words: string[], order: string): boolean {
2 // Create a mapping of each character to its position in the new language order
3 const charPositionMap = new Map<string, number>();
4 for (const char of order) {
5 charPositionMap.set(char, charPositionMap.size);
6 }
7
8 // Iterate through the pairs of adjacent words
9 for (let i = 1; i < words.length; i++) {
10 const firstWord = words[i - 1];
11 const secondWord = words[i];
12
13 // Find the minimum length to compare both words
14 const minLength = Math.min(firstWord.length, secondWord.length);
15 let areWordsEqual = false;
16
17 // Compare characters of both words
18 for (let j = 0; j < minLength; j++) {
19 if (charPositionMap.get(firstWord[j]) > charPositionMap.get(secondWord[j])) {
20 // The first word is greater than the second, so the list is not sorted
21 return false;
22 }
23 if (charPositionMap.get(firstWord[j]) < charPositionMap.get(secondWord[j])) {
24 // The first word comes before the second, so we can break the comparison
25 areWordsEqual = true;
26 break;
27 }
28 }
29
30 // If all characters are equal, but the length of the first word is greater, the list is not sorted
31 if (!areWordsEqual && firstWord.length > secondWord.length) {
32 return false;
33 }
34 }
35
36 // If all words are properly sorted or equal, return true
37 return true;
38}
39
Time and Space Complexity
Time Complexity
The time complexity of the given code consists of a few different components:
-
Creating a mapping (dictionary)
m
from characters to their alien order indices has a complexity ofO(1)
because the number of characters in theorder
string is constant (assuming a fixed alphabet size, e.g., 26 for the English alphabet). -
The outer loop runs a fixed 20 times which is a constant factor and thus does not impact the scalability of the algorithm. The value 20 probably assumes that no word will be longer than 20 characters, which seems to be an arbitrary limit. However, this loop should ideally be in terms of the length of the longest word in
words
. It would be more accurate to consider it asO(L)
whereL
is the length of the longest word inwords
. -
Inside the outer loop, there is an inner loop that iterates over each word in the
words
list. If the number of words isN
, this gives us a complexity ofO(N)
for the inner loop. -
Within the inner loop, the operations are constant time, involving index lookup and comparison.
Putting it all together, even with the arbitrary limit of 20 iterations, the actual scalable factor is the length of the words and the number of words. So the time complexity is O(L * N)
.
Space Complexity
-
The space complexity for creating the
m
dictionary isO(1)
, again because the alphabet size is constant. -
The code does not use any additional significant memory that scales with the input size, as all other variables are of fixed size regardless of the input.
Thus, the overall space complexity of the code is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used in a depth first search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!