What is the pattern used to solve the 'Verifying an Alien Dictionary' problem?

The solution leverages array scanning combined with hash lookups to compare adjacent words in the sequence efficiently based on the custom alien alphabet order.

How do I handle cases where one word is a prefix of another?

When a word is a prefix of another, ensure the longer word comes after the shorter one lexicographically, which means the shorter word should not appear before the longer one if they are equal up to the prefix.

What is the time complexity of the solution for this problem?

The time complexity is O(n * m), where n is the number of words and m is the average length of the words, because each word needs to be compared to the next word character by character.

How can I improve the solution if there are many words?

The current solution is already optimal in terms of time complexity, but ensuring that the word comparison step is as fast as possible using hash lookups is key to scaling for large inputs.

What if the alien alphabet order is not provided in the form of a string?

You would need to transform the input format into a hash table or array representation that maps each character to its index in the alien alphabet for efficient comparison.

#953

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

验证外星语词典

某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（ order ）是一些小写字母的排列。给定一组用外星语书写的单词 words ，以及其字母表的顺序 order ，只有当给定的单词在这种外星语中按字典序排列时，返回 true ；否则，返回 false 。示例 1：输入：…

数组哈希表字符串

题目描述

某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。

给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

示例 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' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。

提示：

1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
在 words[i] 和 order 中的所有字符都是英文小写字母。

lightbulb

解题思路

方法一

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        m = {c: i for i, c in enumerate(order)}
        for i in range(20):
            prev = -1
            valid = True
            for x in words:
                curr = -1 if i >= len(x) else m[x[i]]
                if prev > curr:
                    return False
                if prev == curr:
                    valid = False
                prev = curr
            if valid:
                return True
        return True

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Is the candidate able to efficiently map the alien alphabet?
question_mark
Can they identify and handle edge cases such as prefix issues?
question_mark
Does the candidate approach the problem with an array scanning and hash table solution, avoiding unnecessary complexity?

warning

常见陷阱

外企场景

error
Not properly handling cases where a word is a prefix of another (e.g., 'apple' vs 'app').
error
Failing to correctly implement the lexicographical comparison using the alien alphabet's custom order.
error
Overcomplicating the solution by not recognizing the optimal approach using array scanning and hash lookups.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the list of words is very large? Can the algorithm still scale efficiently?
arrow_right_alt
How would the solution change if we were given words in reverse order?
arrow_right_alt
Can we solve the problem without using a hash table, and if so, what would the time complexity be?

help

常见问题

外企场景

继续练习

#966 元音拼写检查器 #929 独特的电子邮件地址 #916 单词子集