class Solution {
public:
int wordCount(vector<string>& startWords, vector<string>& targetWords) {
}
};
2135. 统计追加字母可以获得的单词数
给你两个下标从 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 的任一字符串中，每个字母至多出现一次原站题解
java 解法, 执行用时: 73 ms, 内存消耗: 53.5 MB, 提交时间: 2023-06-06 09:45:30
class Solution {
public int wordCount(String[] startWords, String[] targetWords) {
Map<Integer, Integer> target = new HashMap();
for(String s : targetWords){
int c = code(s);
target.put(c, target.getOrDefault(c, 0) + 1);
}
int ans = 0;
for(String s : startWords){
int c = code(s);
for(int i = 0; i < 26; i++){
int letter = 1 << i, search = c | letter;
if((c & letter) == 0 && target.containsKey(search)){
ans += target.get(search);
target.remove(search);
}
}
}
return ans;
}
private int code(String s){
int res = 0;
for(char c : s.toCharArray()){
res |= (1 << (c - 'a'));
}
return res;
}
}
python3 解法, 执行用时: 1072 ms, 内存消耗: 45.8 MB, 提交时间: 2023-06-06 09:45:08
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
golang 解法, 执行用时: 96 ms, 内存消耗: 12.9 MB, 提交时间: 2023-06-06 09:44:47
func wordCount(startWords, targetWords []string) (ans int) {
has := map[int]bool{}
for _, word := range startWords {
mask := 0
for _, ch := range word {
mask |= 1 << (ch - 'a')
}
has[mask] = true
}
for _, word := range targetWords {
mask := 0
for _, ch := range word {
mask |= 1 << (ch - 'a')
}
for _, ch := range word {
if has[mask^(1<<(ch-'a'))] { // 去掉这个字符
ans++
break
}
}
}
return
}
cpp 解法, 执行用时: 236 ms, 内存消耗: 96.3 MB, 提交时间: 2023-06-06 09:44:30
class Solution {
public:
int wordCount(vector<string> &startWords, vector<string> &targetWords) {
unordered_set<int> s;
for (string &word : startWords) {
int mask = 0;
for (char ch : word) {
mask |= 1 << (ch - 'a');
}
s.insert(mask);
}
int ans = 0;
for (string &word : targetWords) {
int mask = 0;
for (char ch : word) {
mask |= 1 << (ch - 'a');
}
for (char ch : word) {
if (s.count(mask ^ (1 << (ch - 'a')))) { // 去掉这个字符
++ans;
break;
}
}
}
return ans;
}
};
python3 解法, 执行用时: 568 ms, 内存消耗: 33.6 MB, 提交时间: 2023-06-06 09:44:15
# 逆向思维 + 位运算 + 哈希表
class Solution:
def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
s = set()
for word in startWords:
mask = 0
for ch in word:
mask |= 1 << (ord(ch) - ord('a'))
s.add(mask)
ans = 0
for word in targetWords:
mask = 0
for ch in word:
mask |= 1 << (ord(ch) - ord('a'))
for ch in word:
if mask ^ (1 << (ord(ch) - ord('a'))) in s: # 去掉这个字符
ans += 1
break
return ans