Solution: Verifying an Alien Dictionary
Tags: algorithms, javascript, java, python
Published: 2021-04-09 08:52:31

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/verifying-an-alien-dictionary/discuss/1149850).*

---

#### [Leetcode Problem #953 (*Easy*): Verifying an Alien Dictionary](https://leetcode.com/problems/verifying-an-alien-dictionary/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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 lexicographicaly in this alien language.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:|words = ["hello","leetcode"]<br>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"]<br>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"]<br>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](https://en.wikipedia.org/wiki/Lexicographical_order)).

---

#### ***Constraints:***
>
 - `1 <= words.length <= 100`
 - `1 <= words[i].length <= 20`
 - `order.length == 26`
 - All characters in `words[i]` and `order` are English lowercase letters.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

The naive approach here would be to iterate through pairs of consecutive words in our input array (**W**) and compare the position of each letter in the input alphabet (**O**), moving letter by letter until we find a discrepancy and can determine which word comes first lexicographically.

As this is an Easy question, this method works, but with a **time complexity** of **O(N * M * P)** where **N** is the length of **W**, **M** is the average length of each word in **W**, and **P** is the length of **O**.

Rather than repetitively finding the position of a character in **O**, however, we can create a lookup table of indexes from **O** (**alpha**) at a time complexity of **O(P)** and turn every position lookup into a simple **O(1)** operation. That changes the overall time complexity to **O(N * M + P)**.

Then, as noted before, we can just iterate through word pairs (**a, b**) in **W**, then iterate through comparative characters (**achar, bchar**) in those two words and evaluate them based on their lexicographical indexes (**aix, bix**).

If **aix < bix** or if we reach the end of **a**, then the two words are in correct lexicographical order and we should move to the next pair of words. If **aix > bix** or if we reach the end of **b**, the two words are *not* in correct lexicographical order and we should **return false**.

If we reach the end without exiting, we should **return true**.

---

#### ***Implementation:***

There are only minor differences in the code for all four languages.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var isAlienSorted = function(W, O) {
    let alpha = new Map([["",-1]])
    for (let i = 0; i < O.length; i++)
        alpha.set(O.charAt(i), i)
    for (let i = 1; i < W.length; i++) {
        let a = W[i-1], b = W[i]
        for (let j = 0; j < a.length; j++) {
            let achar = a.charAt(j), bchar = b.charAt(j),
                aix = alpha.get(achar), bix = alpha.get(bchar)
            if (aix < bix) break
            if (aix > bix) return false
        }
    }
    return true
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def isAlienSorted(self, W: List[str], O: str) -> bool:
        alpha = {O[i]: i for i in range(len(O))}
        for i in range(1,len(W)):
            a, b = W[i-1], W[i]
            for j in range(len(a)):
                if j == len(b): return False
                achar, bchar = a[j], b[j]
                aix, bix = alpha[achar], alpha[bchar]
                if aix < bix: break
                if aix > bix: return False
        return True
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public boolean isAlienSorted(String[] W, String O) {
        Map<Character,Integer> alpha = new HashMap<>();
        for (int i = 0; i < O.length(); i++)
            alpha.put(O.charAt(i), i);
        for (int i = 1; i < W.length; i++) {
            String a = W[i-1], b = W[i];
            for (int j = 0; j < a.length(); j++) {
                if (j == b.length()) return false;
                char achar = a.charAt(j), bchar = b.charAt(j);
                if (alpha.get(achar) < alpha.get(bchar)) break;
                if (alpha.get(achar) > alpha.get(bchar)) return false;
            }
        }
        return true;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    bool isAlienSorted(vector<string>& W, string O) {
        unordered_map<char,int> alpha;
        for (int i = 0; i < O.size(); i++)
            alpha[O[i]] = i;
        for (int i = 1; i < W.size(); i++) {
            string a = W[i-1], b = W[i];
            for (int j = 0; j < a.size(); j++) {
                if (j == b.size()) return false;
                char achar = a[j], bchar = b[j];
                if (alpha[achar] < alpha[bchar]) break;
                if (alpha[achar] > alpha[bchar]) return false;
            }
        }
        return true;
    }
};
```