Medium

题目描述

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

对于 targetWords 中的每个字符串，检查是否能够从 startWords 中选择一个字符串并对其执行转换操作，使其等于目标字符串。

转换操作按以下两个步骤描述：

  1. 向字符串末尾添加任何不存在于该字符串中的小写字母。

    • 例如，如果字符串是 “abc”，可以向其添加字母 ’d’、’e’ 或 ‘y’，但不能添加 ‘a’。如果添加了 ’d’，结果字符串将是 “abcd”。

  2. 将新字符串的字母按任意顺序重新排列。

    • 例如，“abcd” 可以重新排列为 “acbd”、“bacd”、“cbda” 等。注意，它也可以重新排列为 “abcd” 本身。

返回 targetWords 中可以通过对 startWords 中的任意字符串执行操作得到的字符串数量。

注意，您只需要验证 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 * 10^4
  • 1 <= startWords[i].length, targetWords[j].length <= 26
  • startWords 和 targetWords 的每个字符串都仅由小写英文字母组成
  • startWords 或 targetWords 的任何字符串中都不会出现重复字母

解题思路

解题思路

这道题的核心是理解转换操作：给起始单词添加一个字母，然后重新排列。由于可以任意重新排列，所以我们只需要关心字符的集合，而不是顺序。

关键观察：

  1. 目标单词的长度必须比起始单词长度大1
  2. 目标单词包含的字符集合应该是起始单词字符集合加上一个新字符
  3. 由于不关心顺序，可以用位掩码或集合来表示字符组合

解法思路：

  1. 位掩码解法（推荐）：用26位的整数表示字符集合，第i位为1表示字符’a’+i存在
  2. 哈希集合解法：直接存储排序后的字符串

对于每个目标单词，我们尝试移除其中每一个字符，看移除后的字符集合是否在起始单词的集合中存在。

算法步骤：

  1. 将所有起始单词转换为位掩码，存储在哈希集合中
  2. 对于每个目标单词，转换为位掩码
  3. 尝试移除目标单词中的每个字符，检查剩余的位掩码是否在起始集合中
  4. 如果找到匹配，计数器加1

时间复杂度主要来自于对每个目标单词尝试移除所有字符的操作。

代码实现

class Solution {
public:
    int wordCount(vector<string>& startWords, vector<string>& targetWords) {
        unordered_set<int> startMasks;
        
        // 将所有起始单词转换为位掩码
        for (const string& word : startWords) {
            int mask = 0;
            for (char c : word) {
                mask |= (1 << (c - 'a'));
            }
            startMasks.insert(mask);
        }
        
        int count = 0;
        for (const string& target : targetWords) {
            int targetMask = 0;
            for (char c : target) {
                targetMask |= (1 << (c - 'a'));
            }
            
            // 尝试移除每个字符，看是否在起始集合中
            for (char c : target) {
                int removedMask = targetMask ^ (1 << (c - 'a'));
                if (startMasks.count(removedMask)) {
                    count++;
                    break;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
        # 将所有起始单词转换为位掩码
        start_masks = set()
        for word in startWords:
            mask = 0
            for c in word:
                mask |= (1 << (ord(c) - ord('a')))
            start_masks.add(mask)
        
        count = 0
        for target in targetWords:
            target_mask = 0
            for c in target:
                target_mask |= (1 << (ord(c) - ord('a')))
            
            # 尝试移除每个字符，看是否在起始集合中
            for c in target:
                removed_mask = target_mask ^ (1 << (ord(c) - ord('a')))
                if removed_mask in start_masks:
                    count += 1
                    break
        
        return count

public class Solution {
    public int WordCount(string[] startWords, string[] targetWords) {
        var startMasks = new HashSet<int>();
        
        // 将所有起始单词转换为位掩码
        foreach (string word in startWords) {
            int mask = 0;
            foreach (char c in word) {
                mask |= (1 << (c - 'a'));
            }
            startMasks.Add(mask);
        }
        
        int count = 0;
        foreach (string target in targetWords) {
            int targetMask = 0;
            foreach (char c in target) {
                targetMask |= (1 << (c - 'a'));
            }
            
            // 尝试移除每个字符，看是否在起始集合中
            foreach (char c in target) {
                int removedMask = targetMask ^ (1 << (c - 'a'));
                if (startMasks.Contains(removedMask)) {
                    count++;
                    break;
                }
            }
        }
        
        return count;
    }
}

var wordCount = function(startWords, targetWords) {
    const startMasks = new Set();
    
    // 将所有起始单词转换为位掩码
    for (const word of startWords) {
        let mask = 0;
        for (const c of word) {
            mask |= (1 << (c.charCodeAt(0) - 97));
        }
        startMasks.add(mask);
    }
    
    let count = 0;
    for (const target of targetWords) {
        let targetMask = 0;
        for (const c of target) {
            targetMask |= (1 << (c.charCodeAt(0) - 97));
        }
        
        // 尝试移除每个字符，看是否在起始集合中
        for (const c of target) {
            const removedMask = targetMask ^ (1 << (c.charCodeAt(0) - 97));
            if (startMasks.has(removedMask)) {
                count++;
                break;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(N×L + M×L²)N为startWords长度，M为targetWords长度，L为平均单词长度。构建哈希集合需要O(N×L)，对每个目标单词尝试移除字符需要O(M×L²)
空间复杂度O(N)存储所有起始单词的位掩码

相关题目