953. Verifying an Alien Dictionary

EasyArrayHash TableString
Leetcode Link

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 position i in the current word, we should immediately return False, 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 return True as this means the list is sorted correctly up to this character.

  • If after checking all positions i, we haven't returned False, it is safe to assume that the list is sorted according to the alien language, and we return True.

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:

  1. 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 the order 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 character c is paired with its index i, effectively creating a rank ordering for the alien alphabet.

  2. 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 position i, it compares characters from different words at the same index.

    for i in range(20):
        # ...
  3. Tracking and Comparing Ranks of Characters: Inside the loop, two variables prev and curr 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
  4. Checking Sorted Order: As we iterate over each word x in words, 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
  5. Validating Sequential Characters: If the previous character is the same as the current one, valid is set to False. 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
  6. Early Termination: If at any point, we successfully pass through all the words and their characters at a certain index without returning False, and valid remains True, it means we found a lexicographical order and can return True immediately. Otherwise, we continue.

    if valid:
        return True
  7. 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 Evaluator

Example 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.

  1. Mapping the Order:

    • Using the provided order, we create a mapping m 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}.
  2. Comparing Characters in Words:

    • We set up a loop that will go up to 20, which is more than enough for our example.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. Final Verdict:

    • After checking all positions and finding no disorder, we return True, meaning the list is sorted according to the alien dictionary.

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 of O(1) because the number of characters in the order 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 as O(L) where L is the length of the longest word in words.

  • Inside the outer loop, there is an inner loop that iterates over each word in the words list. If the number of words is N, this gives us a complexity of O(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 is O(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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used in a depth first search?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!