JavaScript Algorithms: Verifying an Alien Dictionary (LeetCode)

Photo by Pisit Heng on Unsplash

Description

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.

Solution

First of all, let’s find out what lexicographic order is — wiki. What we really need to know about lexicographic order for solving this problem:

• If two words have the same first letter, we compare the second. If the second letters are the same, we compare the third and so on. Finally, one word comes before the other if the first differing letter comes before the corresponding letter.
• If two words are identical up to the length of the shorter word, the shorter word comes first.

In other words — javascript.info:

1. Compare the first character of both strings.
2. If the first character from the first string is greater (or less) than the other string’s, then the first string is greater (or less) than the second. We’re done.
3. Otherwise, if both strings’ first characters are the same, compare the second characters the same way.
4. Repeat until the end of either string.
5. If both strings end at the same length, then they are equal. Otherwise, the longer string is greater.

To compare two letters in JavaScript means to compare their codes in Unicode (16-bit Unicode Transformation Format). So, using Unicode we know that a has feff0061 char code, b has feff0062, and so on.

'a'.charCodeAt().toString(16) -> 61
'b'.charCodeAt().toString(16) -> 62
...
'z'.charCodeAt().toString(16) -> 7a

In this problem, we have a new alphabet order and we need to figure out how we can compare two letters efficiently. The best data structure in this case is HashMap. The key will be a letter and the value will be index since we need to compare two letters and the larger will be the letter with the higher index.

So, after we’ve understood all of that, we can switch to an algorithm. We can loop through all words and compare two words (current and next) in each iteration letter by letter. The comparison algorithm is pretty simple:

• If current[i] === next[i] we need to go further.
• If map[current[i]] < map[next[i]] we need to return false because we don’t need to compare other characters anymore.
• If map[current[i]] > map[next[i]] we need to go to the next word pair if it exists.

Let’s look at the implementation:

The time complexity is O(mn), where m is the number of words and n is the average length of these words. According to the constraints, we can say that the time complexity is linear because we can have at most 20 characters in a word. The space complexity is constant because we have at most 26 letters in order.

I hope, it was useful for you. Thanks for reading! Looking forward to your feedback. See you soon ✌️