|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
- 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).
-
- 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:
- def isAlienSorted(self, words: List[str], order: str) -> bool:
- for i in range(1, len(words)):
- first = words[i - 1]
- second = words[i]
- length = min(len(first), len(second))
- if length == len(second) and first[:length] == second:
- return False
-
- j = 0
- while j < length and first[j] == second[j]:
- j += 1
- if j >= len(first): return True
- index_first = order.find(first[j])
- index_second = order.find(second[j])
-
- if index_first > index_second:
- return False
-
- return True
复制代码 |
|