LeetCode 题解工作台
统计追加字母可以获得的单词数
给你两个下标从 0 开始的字符串数组 startWords 和 targetWords 。每个字符串都仅由 小写英文字母 组成。 对于 targetWords 中的每个字符串，检查是否能够从 startWords 中选出一个字符串，执行一次 转换操作 ，得到的结果与当前 targetWords 字符…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们注意到，题目中给定的字符串只包含小写字母，并且每个字符串的字母至多出现一次。因此，我们可以用一个长度为 的二进制数表示一个字符串，其中第 位为 表示字符串中包含第 个小写字母，为 表示字符串中不包含第 个小写字母。 我们可以将字符串数组 中的每个字符串转换为一个二进制数，并将这些二进制数存储到一个集合 中。对于字符串数组 中的每个字符串，我们首先将其转换为一个二进制数，然后枚…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你两个下标从 0 开始的字符串数组 startWords 和 targetWords 。每个字符串都仅由 小写英文字母 组成。
对于 targetWords 中的每个字符串，检查是否能够从 startWords 中选出一个字符串，执行一次 转换操作 ，得到的结果与当前 targetWords 字符串相等。
转换操作 如下面两步所述：
- 追加 任何 不存在 于当前字符串的任一小写字母到当前字符串的末尾。
- 例如，如果字符串为
"abc"，那么字母'd'、'e'或'y'都可以加到该字符串末尾，但'a'就不行。如果追加的是'd'，那么结果字符串为"abcd"。
- 例如，如果字符串为
- 重排 新字符串中的字母，可以按 任意 顺序重新排布字母。
- 例如，
"abcd"可以重排为"acbd"、"bacd"、"cbda"，以此类推。注意，它也可以重排为"abcd"自身。
- 例如，
找出 targetWords 中有多少字符串能够由 startWords 中的 任一 字符串执行上述转换操作获得。返回 targetWords 中这类 字符串的数目 。
注意：你仅能验证 targetWords 中的字符串是否可以由 startWords 中的某个字符串经执行操作获得。startWords 中的字符串在这一过程中 不 发生实际变更。
示例 1：
输入：startWords = ["ant","act","tack"], targetWords = ["tack","act","acti"] 输出：2 解释： - 为了形成 targetWords[0] = "tack" ，可以选用 startWords[1] = "act" ，追加字母 'k' ，并重排 "actk" 为 "tack" 。 - startWords 中不存在可以用于获得 targetWords[1] = "act" 的字符串。 注意 "act" 确实存在于 startWords ，但是 必须 在重排前给这个字符串追加一个字母。 - 为了形成 targetWords[2] = "acti" ，可以选用 startWords[1] = "act" ，追加字母 'i' ，并重排 "acti" 为 "acti" 自身。
示例 2：
输入：startWords = ["ab","a"], targetWords = ["abc","abcd"] 输出：1 解释： - 为了形成 targetWords[0] = "abc" ，可以选用 startWords[0] = "ab" ，追加字母 'c' ，并重排为 "abc" 。 - startWords 中不存在可以用于获得 targetWords[1] = "abcd" 的字符串。
提示：
1 <= startWords.length, targetWords.length <= 5 * 1041 <= startWords[i].length, targetWords[j].length <= 26startWords和targetWords中的每个字符串都仅由小写英文字母组成- 在
startWords或targetWords的任一字符串中，每个字母至多出现一次
解题思路
方法一：哈希表 + 位运算
我们注意到，题目中给定的字符串只包含小写字母，并且每个字符串的字母至多出现一次。因此，我们可以用一个长度为 的二进制数表示一个字符串，其中第 位为 表示字符串中包含第 个小写字母，为 表示字符串中不包含第 个小写字母。
我们可以将字符串数组 中的每个字符串转换为一个二进制数，并将这些二进制数存储到一个集合 中。对于字符串数组 中的每个字符串，我们首先将其转换为一个二进制数，然后枚举这个字符串中的每个字母，将这个字母从二进制数中去掉，再检查是否存在一个二进制数在集合 中，使得这个二进制数与去掉的字母的二进制数的异或结果在集合 中，如果存在，那么这个字符串可以由 中的某个字符串执行转换操作获得，答案加一。然后我们跳过这个字符串，继续处理下一个字符串。
时间复杂度 ，空间复杂度 。其中 为字符串数组 的长度，而 为字符串中的字符集大小，本题中 。
class Solution:
def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
s = {sum(1 << (ord(c) - 97) for c in w) for w in startWords}
ans = 0
for w in targetWords:
x = sum(1 << (ord(c) - 97) for c in w)
for c in w:
if x ^ (1 << (ord(c) - 97)) in s:
ans += 1
break
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Tests the candidate's understanding of efficient string manipulation and hash table usage.
- question_mark
Focuses on the candidate's ability to optimize array scanning and string transformations.
- question_mark
Evaluates problem-solving skills involving letter addition and checking rearrangements.
常见陷阱
外企场景- error
Failing to account for the fact that only one letter can be added to the startWord.
- error
Inefficient implementation by directly comparing unsorted strings instead of using sorting or hash-based lookups.
- error
Overlooking the need for handling large inputs efficiently, which could lead to time limit exceeded errors.
进阶变体
外企场景- arrow_right_alt
Consider variations where more than one letter can be added to the startWord.
- arrow_right_alt
Allow multiple transformations per word in startWords to generate multiple valid targetWords.
- arrow_right_alt
Change the constraints to allow words of varying lengths to test performance with larger inputs.