# 953. Verifying an Alien Dictionary

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.

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

``````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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation