[leetcode] 953. Verifying an Alien Dictionary

[leetcode] 953. Verifying an Alien Dictionary

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 1:

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"Output: trueExplanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

Example 2:

Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"Output: falseExplanation: 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: falseExplanation: 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).

Constraints:

1 <= words.length <= 1001 <= words[i].length <= 20order.length == 26All characters in words[i] and order are English lowercase letters.

分析

题目的意思是：给定字符串数组words，判断是否按照order顺序排列。思路也很直接，先把order按照顺序映射称为数字，用字典d存放，然后遍历words，每两个单词取出来比较，

把第一个不同的字符拎出来判断一下就行了，如果符合顺序，说明当前的两个单词符合顺序的。另外还要单独判断[‘app’,‘apple’]这种情况，这种情况比较一下长度就行了。

代码

class Solution: def isAlienSorted(self, words: List[str], order: str) -> bool: d=defaultdict(int) for i in range(len(order)): d[order[i]]=i for i in range(len(words)-1): word1=words[i] word2=words[i+1] flag=True for k in range(min(len(word1),len(word2))): if(word1[k]!=word2[k]): flag=False if(d[word1[k]]>d[word2[k]]): return False else: break if(flag and len(word1)>len(word2)): return False return True

参考文献

​​Approach 1: Check Adjacent Words​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。