更多精彩内容,请关注【力扣简单题】。
题目
难度:★★☆☆☆
类型:字符串
某种外星语也使用英文小写字母,但可能顺序 order 不同。字母表的顺序(order)是一些小写字母的排列。
给定一组用外星语书写的单词 words,以及其字母表的顺序 order,只有当给定的单词在这种外星语中按字典序排列时,返回 true;否则,返回 false。
提示
1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
在 words[i] 和 order 中的所有字符都是英文小写字母。
示例
示例 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
解释:当前三个字符 "app" 匹配时,第二个字符串相对短一些,然后根据词典编纂规则 "apple" > "app",因为 'l' > '∅',其中 '∅' 是空白字符,定义为比任何其他字符都小(更多信息)。
解答
外星语和英语的区别是,字母表中各个字母的先后顺序不一样,我们要判断输入的单词列表是否按照外星语的字母顺序排列。
如果理解英语单词按照字典顺序排列的规则,就可以解决这个问题。英语中,单词的排序根据相应位置字母在字母表中出现的顺序进行排序,且单词从左到右优先级递减。
我们可以对每个单词构建一个索引列表,用来存储单词中各个字母在字母表中出现的位置,根据每个单词对应的索引列表对单词进行排序,如果将字母表更换成外星语字母表的顺序,既可获得按照外星语词典排序的结果,通过按照该方法排序的结果和输入的单词列表是否一致可以实现题目要求的判断。
这里我们可以使用python中的sort方法,该方法就有key关键字选项,我们可以传进一个函数作为参数,这样排序时就会首先将每个元素先送到函数中,利用函数的输出进行排序。该函数实现的功能就是将单词转变为索引列表,用lambda表达式进行定义。
class Solution:
def isAlienSorted(self, words, order):
"""
:param words: List[str]
:param order: str
:return: bool
"""
return words == sorted(words, key=lambda w: [order.index(c) for c in w])
如有疑问或建议,欢迎评论区留言~