剑指 Offer II 034. 外星语言是否排序

剑指 Offer II 034. 外星语言是否排序 #

  • 标签:数组、哈希表、字符串
  • 难度:简单

题目大意 #

给定一组用外星语书写的单词字符串数组 words,以及表示外星字母表的顺序的字符串 order

要求:判断 words 中的单词是否都是按照 order 来排序的。如果是,则返回 True,否则返回 False

解题思路 #

如果所有单词是按照 order 的规则升序排列,则所有单词都符合规则。而判断所有单词是升序排列,只需要两两比较相邻的单词即可。所以我们可以先用哈希表存储所有字母的顺序,然后对所有相邻单词进行两两比较,如果最终是升序排列,则符合要求。具体步骤如下:

  • 使用哈希表 order_map 存储字母的顺序。
  • 遍历单词数组 words,比较相邻单词 word1word2 中所有字母在 order_map 中的下标,看是否满足 word1 <= word2
  • 如果全部满足,则返回 True。如果有不满足的情况,则直接返回 False

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        order_map = dict()
        for i in range(len(order)):
            order_map[order[i]] = i
        for i in range(len(words) - 1):
            word1 = words[i]
            word2 = words[i + 1]

            flag = True

            for j in range(min(len(word1), len(word2))):
                if word1[j] != word2[j]:
                    if order_map[word1[j]] > order_map[word2[j]]:
                        return False
                    else:
                        flag = False
                        break

            if flag and len(word1) > len(word2):
                return False
        return True
本站总访问量  次  |  您是本站第  位访问者