Solution: Verifying an Alien Dictionary

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #953 (Easy): Verifying an Alien Dictionary

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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"] 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.

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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;
    }
};