題目

某種外星語也使用英文小寫字母，但可能順序 order 不同。字母表的順序（order）是一些小寫字母的排列。
給定一組用外星語書寫的單詞 words，以及其字母表的順序 order，只有當(dāng)給定的單詞在這種外星語中按字典序排列時，返回 true；否則，返回 false。
示例 1：
輸入：words = [“hello”,“l(fā)eetcode”], 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)前三個字符 “app” 匹配時，第二個字符串相對短一些，然后根據(jù)詞典編纂規(guī)則 “apple” > “app”，因為 ‘l’ > ‘?’，其中 ‘?’ 是空白字符，定義為比任何其他字符都小（更多信息）。
提示：
1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
在 words[i] 和 order 中的所有字符都是英文小寫字母。
來源：力扣（LeetCode）

解題思路

??這個提類似于我們通常比較字符串的規(guī)則，只不過這里重新定義了字符的大小，按照給定的順序來逐個比較字符串，也是高位不為相等判斷結(jié)束則結(jié)束，否則低一位作為最高位去比較。根據(jù)題目的要求我們需要建立一個能夠很快對比字符大小的函數(shù)，這里可以使用哈希映射來做，由大到小分別映射order里的26個字母。

class Solution:def isAlienSorted(self, words: List[str], order: str) -> bool:if len(words)<2:return Trued={}for i in range(len(order)):  #建立映射關(guān)系字母靠前則數(shù)值越大類似ascll。d[order[i]]=26-ifor i in range(1,len(words)):count=0  #記錄單個單詞相等的字符數(shù)for x,y in zip(words[i-1],words[i]):if d[x]>d[y]:  #如果高位比出來結(jié)果則當(dāng)前單詞比較結(jié)束breakelif d[x]==d[y]:  #如果相等則記錄字符數(shù)count+=1else:   #如果高位比出來結(jié)果則當(dāng)前單詞比較結(jié)束return Falseif len(words[i-1])>len(words[i]) and count==len(words[i]):return Falsereturn True

總結(jié)

以上是生活随笔為你收集整理的LeetCode简单题之验证外星语词典的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。