953 Verifying an Alien Dictionary 驗(yàn)證外星語詞典
Description:
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:
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).
Note:
1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
All characters in words[i] and order are english lowercase letters.
題目描述:
某種外星語也使用英文小寫字母钞馁，但可能順序 order 不同僧凰。字母表的順序（order）是一些小寫字母的排列熟丸。
給定一組用外星語書寫的單詞 words光羞，以及其字母表的順序 order，只有當(dāng)給定的單詞在這種外星語中按字典序排列時(shí)全闷，返回 true萍启；否則，返回 false勘纯。
示例 :
示例 1：
輸入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
輸出：true
解釋：在該語言的字母表中驳遵，'h' 位于 'l' 之前，所以單詞序列是按字典序排列的堤结。
示例 2：
輸入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
輸出：false
解釋：在該語言的字母表中，'d' 位于 'l' 之后唐责，那么 words[0] > words[1]鼠哥，因此單詞序列不是按字典序排列的。
示例 3：
輸入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
輸出：false
解釋：當(dāng)前三個(gè)字符 "app" 匹配時(shí)抄罕，第二個(gè)字符串相對(duì)短一些呆贿，然后根據(jù)詞典編纂規(guī)則 "apple" > "app"恍飘，因?yàn)?'l' > '?'，其中 '?' 是空白字符，定義為比任何其他字符都恤婕簟（更多信息）前弯。
提示：
1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
在 words[i] 和 order 中的所有字符都是英文小寫字母。
思路:
- 改寫比較器的方法, 按照 order的順序比較兩個(gè)字符串的長度和對(duì)應(yīng)位置的大小
- 按照 order的順序重新給 words中的單詞賦值, 再比較兩個(gè)字符串的大小
時(shí)間復(fù)雜度O(mn), 空間復(fù)雜度O(1), 其中 n為 words數(shù)組的大小, m為數(shù)組中的每一個(gè)字符串的長度
代碼:
C++:
class Solution
{
public:
bool isAlienSorted(vector<string>& words, string order)
{
int index[128] = {0};
for (int i = 0; i < 26; i++) index[order[i]] = i + 'a';
for (int i = 0; i < words.size(); i++) for (int j = 0; j < words[i].size(); j++) words[i][j] = index[words[i][j]];
for (int i = 1; i < words.size(); i++) if (words[i - 1] > words[i]) return false;
return true;
}
};
Java:
class Solution {
public boolean isAlienSorted(String[] words, String order) {
Comparator<String> comparator = (a, b) -> {
for (int i = 0; i < Math.min(a.length(), b.length()); i++) if (a.charAt(i) != b.charAt(i)) return order.indexOf(a.charAt(i)) - order.indexOf(b.charAt(i));
return a.length() - b.length();
};
for (int i = 1; i < words.length; i++) if (comparator.compare(words[i - 1], words[i]) > 0) return false;
return true;
}
}
Python:
class Solution:
def isAlienSorted(self, words: List[str], order: str) -> bool:
return words == sorted(words, key=lambda word: [order.index(x) for x in word])
