Problem Explanation

There is an alien language which uses the same english lowercase letters, but possibly in a different order. The order of the alphabet in this alien language is some permutation of all lowercase letters. The task is to check if the words given in an array are sorted lexicographically according to this alien language's alphabetical order. If yes, return true and if not, return false.

For example, if the words = ["hello","leetcode"] and the order = "hlabcdefgijkmnopqrstuvwxyz", the output will be true as h comes before l, so the sequence is sorted.

Approach

The basic concept behind the solution is to map each character from the order to its corresponding english alphabet index. This way, we can translate the words from the alien language to words in English language. Once this translation is done, we can simply check if the words array is sorted leicographically.

Example

For instance, if the order is "worldabcefghijkmnpqstuvxyz": w is first letter, o is the second and r is third and so on. If we try to map it in order as English alphabets, it will be as following:

[23, 14, 17, 11, 3, 0, 1, 2, .. ]

So, world would effectively translate to abcde and with this translation, we can check if the given words are sorted or not.

Python Solution

1
2python
3class Solution(object):
4    def isAlienSorted(self, words, order):
5        order_map = {c: i for i, c in enumerate(order)}
6        
7        for i in range(len(words) - 1):
8            word1 = words[i]
9            word2 = words[i + 1]
10
11            for k in range(min(len(word1), len(word2))):
12                if word1[k] != word2[k]:
13                    if order_map[word1[k]] > order_map[word2[k]]:
14                        return False
15                    break
16                else:
17                    if len(word1) > len(word2):
18                        return False
19        return True

Java Solution

1
2java
3class Solution {
4    public boolean isAlienSorted(String[] words, String order) {
5        int[] index = new int[26];
6        for (int i = 0; i < order.length(); ++i)
7            index[order.charAt(i) - 'a'] = i;
8        
9        for (int i = 0; i < words.length - 1; ++i) {
10            for (int j = i + 1; j < words.length; ++j) {
11                int min = Math.min(words[i].length(), words[j].length());
12                for (int k = 0; k < min; ++k) {
13                    char ic = words[i].charAt(k), jc = words[j].charAt(k);
14                    if (ic != jc) {
15                        if (index[ic - 'a'] > index[jc - 'a'])
16                            return false;
17                        } 
18                    }
19                    if (words[i].length() > words[j].length())
20                        return false;
21                }
22            }
23        }
24        return true;
25    }
26}

Javasript Solution

1
2javascript
3class Solution {
4    isAlienSorted(words, order) {
5        const mapOrder = {};
6        for (let i = 0; i < order.length; i++) {
7            mapOrder[order[i]] = i;
8        }
9        for (let i = 0; i < words.length - 1; i++) {
10            const word1 = words[i];
11            const word2 = words[i+1];
12            let found = false;
13            for (let j = 0; j < Math.min(word1.length, word2.length); j++) {
14                if (word1[j] !== word2[j]) {
15                    if (mapOrder[word1[j]] > mapOrder[word2[j]]) {
16                        return false;
17                    }
18                    found = true;
19                    break;
20                }
21            }
22            if (!found && word1.length > word2.length) {
23                return false;
24            }
25        }
26        return true;
27    }
28}

C++ Solution

1
2c++
3class Solution {
4public:
5    bool isAlienSorted(vector<string>& words, string order) {
6        vector<int> mapOrder(26);
7        for (int i = 0; i < order.size(); ++i)
8            mapOrder[order[i] - 'a'] = i;
9        for (auto& word : words)
10            for (auto& c : word)
11                c = mapOrder[c - 'a'];
12        return is_sorted(words.begin(), words.end());
13    }
14};

C# Solution

1
2csharp
3public class Solution {
4    public bool IsAlienSorted(string[] words, string order) {
5        int[] mapOrder = new int[26];
6        for (int i = 0 ; i < order.Length; ++i)
7            mapOrder[order[i] - 'a'] = i;
8        for (int i = 0; i < words.Length - 1; ++i) {
9            for (int j = i + 1; j < words.Length; ++j) {
10                int min = Math.Min(words[i].Length, words[j].Length), k = 0;
11                for (; k < min; ++k) {
12                    if (words[i][k] != words[j][k]) {
13                        if (mapOrder[words[i][k] - 'a'] > mapOrder[words[j][k] - 'a']) 
14                            return false;
15                        else break;
16                    }
17                }
18                if (k == min && words[i].Length > words[j].Length) return false;
19            }
20        }
21        return true;
22    }
23}

Note

In python, java, c# and JavaScript solution mapOrder/map/index dictionary has been used to easily and efficiently map each character order. Mapped order has been used to check whether the words are sorted or not. In C++ solution, the words are being translated to their english equivalent using the mapOrder and then the inbuilt function is_sorted() is used to determine the sort order of translated words.# Conclusion

The problem of verifying whether a sequence of words is sorted lexicographically according to a given alphabet order, where the alphabet could be in different order, provides a common scenario where the traditional way of sorting does not work. Solving this problem in Python, Java, JavaScript, C++ and C# involved developing a mapping from the order of given alphabet to that of English lowercase letters and then using this mapping to translate the words from alien language to English language. Once the translation is done, the comparison of the words in either language became straight forward. Such an approach can be applied to similar problems where the order of elements differs from the common known order, thus adding a layer of translation before any comparison or operations.