| comments | difficulty | edit_url | rating | source | tags | |||||
|---|---|---|---|---|---|---|---|---|---|---|
true |
困难 |
2233 |
第 152 场周赛 Q4 |
|
外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。
字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：
- 单词
word中包含谜面puzzle的第一个字母。 - 单词
word中的每一个字母都可以在谜面puzzle中找到。
例如，如果字谜的谜面是 "abcdefg"，那么可以作为谜底的单词有 "faced", "cabbage", 和 "baggage"；而 "beefed"（不含字母 "a"）以及 "based"（其中的 "s" 没有出现在谜面中）都不能作为谜底。
返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。
示例：
输入： words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"] 输出：[1,1,3,2,4,0] 解释： 1 个单词可以作为 "aboveyz" 的谜底 : "aaaa" 1 个单词可以作为 "abrodyz" 的谜底 : "aaaa" 3 个单词可以作为 "abslute" 的谜底 : "aaaa", "asas", "able" 2 个单词可以作为 "absoryz" 的谜底 : "aaaa", "asas" 4 个单词可以作为 "actresz" 的谜底 : "aaaa", "asas", "actt", "access" 没有单词可以作为 "gaswxyz" 的谜底，因为列表中的单词都不含字母 'g'。
提示：
1 <= words.length <= 10^54 <= words[i].length <= 501 <= puzzles.length <= 10^4puzzles[i].length == 7words[i][j],puzzles[i][j]都是小写英文字母。- 每个
puzzles[i]所包含的字符都不重复。
根据题目描述，对于字谜数组
由于每个单词重复的字母只需要统计一次，因此，我们可以使用二进制状态压缩的方法，将每个单词
接下来，遍历字谜数组
遍历结束后，我们就可以得到字谜数组
时间复杂度
class Solution:
def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
cnt = Counter()
for w in words:
mask = 0
for c in w:
mask |= 1 << (ord(c) - ord("a"))
cnt[mask] += 1
ans = []
for p in puzzles:
mask = 0
for c in p:
mask |= 1 << (ord(c) - ord("a"))
x, i, j = 0, ord(p[0]) - ord("a"), mask
while j:
if j >> i & 1:
x += cnt[j]
j = (j - 1) & mask
ans.append(x)
return ansclass Solution {
public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
Map<Integer, Integer> cnt = new HashMap<>(words.length);
for (var w : words) {
int mask = 0;
for (int i = 0; i < w.length(); ++i) {
mask |= 1 << (w.charAt(i) - 'a');
}
cnt.merge(mask, 1, Integer::sum);
}
List<Integer> ans = new ArrayList<>();
for (var p : puzzles) {
int mask = 0;
for (int i = 0; i < p.length(); ++i) {
mask |= 1 << (p.charAt(i) - 'a');
}
int x = 0;
int i = p.charAt(0) - 'a';
for (int j = mask; j > 0; j = (j - 1) & mask) {
if ((j >> i & 1) == 1) {
x += cnt.getOrDefault(j, 0);
}
}
ans.add(x);
}
return ans;
}
}class Solution {
public:
vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
unordered_map<int, int> cnt;
for (auto& w : words) {
int mask = 0;
for (char& c : w) {
mask |= 1 << (c - 'a');
}
cnt[mask]++;
}
vector<int> ans;
for (auto& p : puzzles) {
int mask = 0;
for (char& c : p) {
mask |= 1 << (c - 'a');
}
int x = 0;
int i = p[0] - 'a';
for (int j = mask; j; j = (j - 1) & mask) {
if (j >> i & 1) {
x += cnt[j];
}
}
ans.push_back(x);
}
return ans;
}
};func findNumOfValidWords(words []string, puzzles []string) (ans []int) {
cnt := map[int]int{}
for _, w := range words {
mask := 0
for _, c := range w {
mask |= 1 << (c - 'a')
}
cnt[mask]++
}
for _, p := range puzzles {
mask := 0
for _, c := range p {
mask |= 1 << (c - 'a')
}
x, i := 0, p[0]-'a'
for j := mask; j > 0; j = (j - 1) & mask {
if j>>i&1 > 0 {
x += cnt[j]
}
}
ans = append(ans, x)
}
return
}function findNumOfValidWords(words: string[], puzzles: string[]): number[] {
const cnt: Map<number, number> = new Map();
for (const w of words) {
let mask = 0;
for (const c of w) {
mask |= 1 << (c.charCodeAt(0) - 97);
}
cnt.set(mask, (cnt.get(mask) || 0) + 1);
}
const ans: number[] = [];
for (const p of puzzles) {
let mask = 0;
for (const c of p) {
mask |= 1 << (c.charCodeAt(0) - 97);
}
let x = 0;
const i = p.charCodeAt(0) - 97;
for (let j = mask; j; j = (j - 1) & mask) {
if ((j >> i) & 1) {
x += cnt.get(j) || 0;
}
}
ans.push(x);
}
return ans;
}