2135 统计追加字母可以获得的单词数¶
考点：位运算 + 哈希表
// console.log(wordCount(["ant","act","tack"], ["tack","act","acti"]) === 2)
// console.log(wordCount(["ab","a"], ["abc","abcd"]) === 1)
考虑 targetWords[i] 能否还原回 startWords 中的某个字符串。
由于可以任意重排，我们可以对 startWords 和 targetWords 的每个字符串都排序。
由于需要追加字符，且题目保证所有字符串都没有重复字符，因此我们可以枚举排序后的 targetWords[i] 的所有字符，将其去掉后去看看是否在每个字符串都排序后的 startWords 中存在。这可以用哈希表实现。
代码实现时，我们并不需要排序每个字符串，而是记录每个字符是否出现过，这可以用位运算实现。
高赞解答
class Solution:
def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
s = set()
for word in startWords:
mask = 0
for ch in word:
# ord 函数，获取字符串对应的十进制整数（ASCll数值）
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
官方解答
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
作者：LeetCode-Solution 链接：https://leetcode.cn/problems/count-words-obtained-after-adding-a-letter/solution/tong-ji-zhui-jia-zi-mu-ke-yi-huo-de-de-d-9ivl/ 来源：力扣（LeetCode）
个人思路：js 使用字符串方法实现，会超时，看能否改进算法
思路1：91/93 cases passed 当数组很长时（出错的例子，数组长度是5万，每一项有6个字母），会超时，需要优化算法
如果直接给字符串增加一个字符，然后获取任意的排列结果，那么性能很差
'asdfgh' 去掉一个字符，然后排序，然后写入到字典中，这有多少种情况？
var wordCount = function(startWords, targetWords) {
let map = {};
for (let j = 0; j < targetWords.length; j++) {
const str = targetWords[j];
for (let i = 0; i < str.length; i++) {
let curr = str.slice(0, i) + str.slice(i + 1);
// 字符串需要转换成数组，排序，然后转换成字符串，写入字典中，这里性能很差
curr = curr.split().sort((a, b) => a > b ? 1 : -1).join('');
console.log(curr);
if (map[curr]) {
map[curr] = map[curr] + 1;
} else {
map[curr] = 1;
}
}
}
console.log(map);
let result = 0;
for (let i = 0; i < startWords.length; i++) {
const str = startWords[i].split().sort((a, b) => a > b ? 1 : -1).join('');
if (map[str]) {
result += map[str];
}
}
return result;
}
/*
* @lc app=leetcode.cn id=2135 lang=javascript
* [2135] 统计追加字母可以获得的单词数
*/
// @lc code=start
/**
* @param {string[]} startWords
* @param {string[]} targetWords
* @return {number}
*/
// 1、遍历 target 数组，拿到每一个单词，进行判断
// 2、先通过长度过滤（遍历 start 数组）
// 长度必须等于 target[index] - 1 才行
// 然后对比这两个字符串，求交集和并集，如果不相同的元素等于1，就是满足的；如果不相同的元素大于1，就不满足（写一个判断的辅助函数）
// 3、累计满足的单词数量
// 不足点：每次需要计算 start[index] 中的数量，性能较差，最好转换成字典存储，这样一次即可，不需要每次遍历，因为这个是固定的
var wordCount = function(startWords, targetWords) {
function check(short_str, long_str) {
let dict = {};
for (let i = 0; i < long_str.length; i++) {
let key = long_str[i];
if (!dict[key]) {
dict[key] = 1;
} else {
dict[key] = dict[key] + 1;
}
}
for (let i = 0; i < short_str.length; i++) {
if (dict[short_str[i]]) {
dict[short_str[i]] = dict[short_str[i]] - 1;
} else {
return false; // 存在其他的字符串，不满足条件
}
}
return true; // 满足条件
}
let result = 0;
for (let i = 0; i < targetWords.length; i++) {
const current = targetWords[i];
for (let j = 0; j < startWords.length; j++) {
if (startWords[j].length + 1 === current.length) {
// console.log(startWords[j], current, check(startWords[j], current));
if (check(startWords[j], current)) {
result += 1;
break;
}
}
}
}
return result;
};