统计追加字母可以获得的单词数

标签: 位运算 数组 哈希表 字符串 排序

难度: Medium

给你两个下标从 0 开始的字符串数组 startWords 和 targetWords 。每个字符串都仅由 小写英文字母 组成。

对于 targetWords 中的每个字符串，检查是否能够从 startWords 中选出一个字符串，执行一次 转换操作 ，得到的结果与当前 targetWords 字符串相等。

转换操作 如下面两步所述：

  1. 追加 任何 不存在 于当前字符串的任一小写字母到当前字符串的末尾。
    • 例如，如果字符串为 "abc" ，那么字母 'd'、'e' 或 'y' 都可以加到该字符串末尾，但 'a' 就不行。如果追加的是 'd' ，那么结果字符串为 "abcd" 。
  2. 重排 新字符串中的字母，可以按 任意 顺序重新排布字母。
    • 例如，"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 * 104
  • 1 <= startWords[i].length, targetWords[j].length <= 26
  • startWords 和 targetWords 中的每个字符串都仅由小写英文字母组成
  • 在 startWords 或 targetWords 的任一字符串中，每个字母至多出现一次

Submission

运行时间: 375 ms

内存: 33.1 MB

class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
        se=set()
        for word in startWords:
            a=0
            for i in word:
                a|=1<<(ord(i)-ord("a"))
            se.add(a)
        ret=0
        for word in targetWords:
            a=0
            for i in word:
                a|=1<<(ord(i)-ord("a"))
            for i in word:
                if a ^ (1<<(ord(i)-ord("a"))) in se:
                    ret+=1
                    break
        return ret

Explain

题解采用位运算来优化字符串比较的速度。首先，将 startWords 中的每个单词转换为一个整数，该整数的每个位表示一个字母是否存在于单词中。例如，若单词中含有字母 'a'，则整数的第0位为1；若含有 'b'，则第1位为1，依此类推。这样，每个单词可以表示为一个长度为26的位向量。同样的转换也应用于 targetWords。对于 targetWords 中的每个单词，检查通过移除任意一个字母后是否能在之前生成的 startWords 的整数集合中找到对应的整数。如果可以找到，说明该 targetWord 可以由 startWord 通过添加一个字母并重新排列得到。

时间复杂度: O((N + M) * L)

空间复杂度: O(N)

class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
        se=set()
        # 将 startWords 中的每个单词转化为一个整数，并存入集合 se 中
        for word in startWords:
            a=0
            for i in word:
                a|=1<<(ord(i)-ord('a'))
            se.add(a)
        ret=0
        # 检查每个 targetWords 是否可以由 startWords 中的某个单词转换得来
        for word in targetWords:
            a=0
            for i in word:
                a|=1<<(ord(i)-ord('a'))
            # 尝试移除 targetWords 中的每个字母，看结果是否在集合 se 中
            for i in word:
                if a ^ (1<<(ord(i)-ord('a'))) in se:
                    ret+=1
                    break
        return ret

Explore

位运算表示方法具有存储效率高和处理速度快的优点。使用位运算，每个单词可以被压缩到一个整数中，这样不仅节省了空间，而且能够快速进行单词之间的比较操作，如检查某个字母是否存在。相比之下，哈希表虽然检索快但空间消耗较大，数组则在每次查找时可能需要遍历整个数组。位运算通过位操作直接对整数进行，可以极大地提高效率。

这种方法是为了找出能否通过从targetWords的单词移除一个字母并重新排列得到startWords中的某个单词。通过检查移除每个字母后的单词是否存在于startWords的转换集合中，可以有效地确定是否有对应的匹配单词。尽管这种方法涉及多次操作，但由于使用位运算和集合操作，它仍然是效率较高的。考虑到每个单词的长度通常很短，这种方法的时间复杂度是可接受的。

位运算的表示方法只关心字母是否出现，而不关心字母出现的次数。当从含有重复字母的单词中移除一个字母时，位运算表示的整数中相应的位只会从1变为0，如果原单词中该字母出现多次，那么在移除一个后，位表示不会变化。因此，这种情况下的处理仍然是有效的，因为我们关心的是能否通过重新排列和添加一个字母来匹配，而不是字母的具体数量。