[LeetCode] 953. Verifying an Alien Dictionary

[grandyang]

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.

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

这道题说是有一个外星文字典，其字母顺序和英语中的字母顺序不同，但还是使用原来的 26 个字母，现在给了这个外星文的字典顺序，又给了一个单词数组，问这些单词是否是按字母顺序排列的。对于正常的字母顺序，就是按字母来比较，只要有字母不同的话，就可以知道两个单词的顺序了，假如比较的字母均相同，但是有一个单词提前结束了，而另一个单词后面还有字母，则短的那个单词排前面。整体比较的思路仍然相同，就是字母顺序要用其给定的顺序，所以用一个 HashMap 来建立字母和其对应位置之间的映射，这样在比较字母顺序的时候就可以从 HashMap 中直接取值。在验证顺序的时候，只需要两两进行验证，若某一对的顺序不符合，则直接返回 false。具体的比较方法还是跟之前说的，逐个字母进行比较，为了避免越界，遍历的时候只能遍历到二者中较短的长度。若对应位上的字母相同，则直接跳过；若前面的字母顺序靠后，则直接返回 false，否则 break 掉（注意这里不能直接返回 true 的原因是后面有可能还会出现不合题目要求的情况）。之后还要验证前面提到的一种情况，就是当较短的单词是较长单词的子串时，而且后面的单词较短时，也需要返回 false。当外层 for 循环正常退出后，返回 true 即可，参见代码如下：

解法一：

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        unordered_map<char, int> charMap;
        for (int i = 0; i < order.size(); ++i) {
            charMap[order[i]] = i;
        }
        for (int i = 1; i < words.size(); ++i) {
            string word1 = words[i - 1], word2 = words[i];
            int n1 = word1.size(), n2 = word2.size();
            for (int j = 0; j < n1 && j < n2; ++j) {
                if (word1[j] == word2[j]) continue;
                if (charMap[word1[j]] > charMap[word2[j]]) return false;
                else break;
            }
            if (n1 > n2 && word1.substr(0, n2) == word2) return false;
        }
        return true;
    }
};

再来看一种比较巧妙的方法，调用了 STL 内部的 is_sorted 函数，由于这个函数是针对正常的字母顺序的，所以要根据外星文的顺序来调换 words 中的字母，使其变为对应的正常的字母顺序。是不是不太好理解，比如外星文的顺序是 bac，则b对应0，a对应1，c对应2，现在给两个单词，ba 和 ac，一眼可以看出这不符合正常的字母顺序，但是其符合外星文的顺序，所以要将其转化为 01 和 12，这里不是数字，而是当作 ASCII 码，跟表示字母的一样，此时再比较的话就是正常的字母顺序了，完美解决，参见代码如下：

解法二：

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        vector<int> charMap(26);
        for (int i = 0; i < order.size(); ++i) {
            charMap[order[i] - 'a'] = i;
        }
        for (string &word : words) {
            for (char &c : word) {
                c = charMap[c - 'a'];
            }
        }
        return is_sorted(words.begin(), words.end());
    }
};

Github 同步地址:

#953

参考资料：

https://leetcode.com/problems/verifying-an-alien-dictionary/

https://leetcode.com/problems/verifying-an-alien-dictionary/discuss/203185/JavaC%2B%2BPython-Mapping-to-Normal-Order

https://leetcode.com/problems/verifying-an-alien-dictionary/discuss/203246/JavaPython-3-Clean-codes-w-comment-time%3A-O(mn)-space%3A-O(1).

LeetCode All in One 题目讲解汇总(持续更新中...)