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

给你两个下标从 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 的任一字符串中，每个字母至多出现一次

方法一：维护所有可构成的状态

思路与算法

由于每个字符串仅含有互不重复的小写英文字母，且转换操作包含任意顺序的重排，因此「目标字符串是否可以获得」与「起始字符串是否可以构成目标字符串」仅取决于对应字符串含有哪些英文字母。

我们可以用一个 26 位的二进制整数维护每个单词含有哪些英文字母。具体地，整数的第 i 位为 1 代表该字符串含有第 i 个英文字母；反之亦然。那么，我们只需要用哈希集合维护 startWords 中每个字符串在转换操作后的所有可能状态，并计算 startWords 中有多少字符串对应的状态包含在该哈希表中即可。

具体地，我们用函数 mask}(\textit{word}) 来计算字符串 word 对应的状态值，其中我们用整数 res 来维护这一状态：在遍历 word 时，碰到字母表中第 i 个字符，我们就对 res 从低到高的第 i 位对 1 取或，即 res} = \textit{res} | (1 << i)。最终，我们返回 res 作为字符串 word 包含英文字母的状态。

进一步地，我们用哈希集合 masks 来维护 startWords 中每个字符串在转换操作后的所有可能状态，对于 startWords 每个字符串的状态 msk，我们遍历它的所有二进制位，如果从低到高第 i 个二进制位为 0，则说明它不含有第 i 个字母，我们可以将该字母添加进字符串中，并将新的状态 msk} | (1 << i) 添加进哈希集合 masks 中作为可以获得的状态；如果该二进制位为 1，则我们无法将对应英文字母添加进该字符串中，因此我们不进行任何操作。

最终，我们遍历 startWords 中的字符串，计算它对应的包含字母状态，并检查其是否存在于 masks 中。在遍历的过程中，我们统计状态位于 masks 中的字符串数量，并返回该数量作为答案。

代码

[sol1-C++]

class Solution {
public:
    int wordCount(vector<string>& startWords, vector<string>& targetWords) {
        // 将 word 转化为表示包含字母状态的二进制整数
        auto mask = [](const string& word) -> int {
            int res = 0;
            for (char ch: word) {
                res |= 1 << (ch - 'a');
            }
            return res;
        };
        
        unordered_set<int> masks;   // 所有可以获得的状态
        for (const string& start: startWords) {
            // 遍历初始单词，根据其状态值构造所有可以获得的状态
            int msk = mask(start);
            for (int i = 0; i < 26; ++i) {
                if (((msk >> i) & 1) == 0) {
                    masks.insert(msk | (1 << i));
                }
            }
        }
        int cnt = 0;   // 可以获得的单词数
        for (const string& target: targetWords) {
            if (masks.count(mask(target))) {
                ++cnt;
            }
        }
        return cnt;
    }
};

[sol1-Python3]

class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
        # 将 word 转化为表示包含字母状态的二进制整数
        def mask(word: str) -> int:
            res = 0
            for ch in word:
                res |= 1 << (ord(ch) - ord('a'))
            return res
        
        masks = set()   # 所有可以获得的状态
        for start in startWords:
            # 遍历初始单词，根据其状态值构造所有可以获得的状态
            msk = mask(start)
            for i in range(26):
                if ((msk >> i) & 1) == 0:
                    masks.add(msk | (1 << i))
        cnt = 0   # 可以获得的单词数
        for target in targetWords:
            if mask(target) in masks:
                cnt += 1
        return cnt

复杂度分析

• 时间复杂度：O(n|\Sigma| + m)，其中 n 为数组 startWords 的长度，m 为数组 targetWords 的长度，|\Sigma| 为字符集的大小。其中，维护所有可能状态的哈希集合的时间复杂度为 O(n|\Sigma|)，维护可构成目标字符串数量的时间复杂度为 O(m)。

• 空间复杂度：O(n|\Sigma|)，即为存储所有可构成状态的哈希集合的空间开销。