2135. 统计追加字母可以获得的单词数（Rating 1828）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

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

Rating 1828

思路

按照题意，输入的字符串中任意字母至多出现1次，且字母顺序并不重要。

因此可以用一个32位数表示字符串，每一位表示一个字母，如第0位表示a，第1位表示b，以此类推。

因此本题就转换为了一个位运算的问题。考虑

遍历start中的字符串，获得其对应的num

遍历26个字母，如果对应字母位为0，考虑将其置为1时是否在target中存在即可。

代码

class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
        m, n = len(startWords), len(targetWords)
        targetNums = defaultdict(lambda: 0) # 维护一个target字典，包含每个字符串的数量
        for idx, word in enumerate(targetWords):
            num = 0
            for c in word:
                num += 1 << (ord(c) - ord('a'))
            targetNums[num] += 1
        ret = 0
        for idx, word in enumerate(startWords):
            num = 0
            for c in word: # 遍历字符串，获得其对应的32位数
                num += 1 << (ord(c) - ord('a'))
            for b in range(26):
                if (num >> b) & 1: # 只判断对应位为0的位置
                    continue
                if num + (1 << b) in targetNums: # 存在，则更新答案 & 更新target字典
                    ret += targetNums[num + (1 << b)]
                    targetNums.pop(num + (1 << b))
        return ret