GuilinDev
Lc1178
05 August 2008
Number of Valid Words for Each Puzzle
只包含小写字母，用一个26位的array来表示某个字母是否存在
时间复杂度：O(M + N)。 空间复杂度：O(M)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
HashMap<Integer, Integer> map = new HashMap<>();
for (String word : words) {
int key = 0;
for (char ch : word.toCharArray()) {
key |= 1 << ch - 'a';
}
map.put(key, map.getOrDefault(key, 0) + 1);
}
List<Integer> result = new ArrayList<>(puzzles.length);
for (String puzzle : puzzles) {
result.add(dfs(puzzle, 1, map, 1 << puzzle.charAt(0) - 'a')); //必须有首字符
}
return result;
}
private int dfs(String puzzle, int index, HashMap<Integer, Integer> map, int key) {
if (index == puzzle.length()) {
return map.getOrDefault(key, 0);
}
// 首字符之外的字符选择有选或不选两种情况
return dfs(puzzle, index + 1, map, key) + dfs(puzzle, index + 1, map, key | 1 << puzzle.charAt(index) - 'a');
}
}