golang 解法, 执行用时: 96 ms, 内存消耗: 16.8 MB, 提交时间: 2023-09-22 10:29:12

// 状态压缩
func findNumOfValidWords(words []string, puzzles []string) []int {
    const puzzleLength = 7
    cnt := map[int]int{}
    for _, s := range words {
        mask := 0
        for _, ch := range s {
            mask |= 1 << (ch - 'a')
        }
        if bits.OnesCount(uint(mask)) <= puzzleLength {
            cnt[mask]++
        }
    }

    ans := make([]int, len(puzzles))
    for i, s := range puzzles {
        first := 1 << (s[0] - 'a')

        // 枚举子集方法一
        //for choose := 0; choose < 1<<(puzzleLength-1); choose++ {
        //    mask := 0
        //    for j := 0; j < puzzleLength-1; j++ {
        //        if choose>>j&1 == 1 {
        //            mask |= 1 << (s[j+1] - 'a')
        //        }
        //    }
        //    ans[i] += cnt[mask|first]
        //}

        // 枚举子集方法二
        mask := 0
        for _, ch := range s[1:] {
            mask |= 1 << (ch - 'a')
        }
        subset := mask
        for {
            ans[i] += cnt[subset|first]
            subset = (subset - 1) & mask
            if subset == mask {
                break
            }
        }
    }
    return ans
}


// 字典树
type trieNode struct {
    son [26]*trieNode
    cnt int
}

func findNumOfValidWords2(words []string, puzzles []string) []int {
    root := &trieNode{}
    for _, word := range words {
        // 将 word 中的字母按照字典序排序并去重
        w := []byte(word)
        sort.Slice(w, func(i, j int) bool { return w[i] < w[j] })
        i := 0
        for _, ch := range w[1:] {
            if w[i] != ch {
                i++
                w[i] = ch
            }
        }
        w = w[:i+1]

        // 加入字典树中
        cur := root
        for _, ch := range w {
            ch -= 'a'
            if cur.son[ch] == nil {
                cur.son[ch] = &trieNode{}
            }
            cur = cur.son[ch]
        }
        cur.cnt++
    }

    ans := make([]int, len(puzzles))
    for i, puzzle := range puzzles {
        pz := []byte(puzzle)
        first := pz[0]
        sort.Slice(pz, func(i, j int) bool { return pz[i] < pz[j] })

        // 在回溯的过程中枚举 pz 的所有子集并统计答案
        var find func(int, *trieNode) int
        find = func(pos int, cur *trieNode) int {
            // 搜索到空节点，不合法，返回 0
            if cur == nil {
                return 0
            }

            // 整个 pz 搜索完毕，返回谜底的数量
            if pos == len(pz) {
                return cur.cnt
            }

            // 选择第 pos 个字母
            res := find(pos+1, cur.son[pz[pos]-'a'])

            // 当 pz[pos] 不为首字母时，可以不选择第 pos 个字母
            if pz[pos] != first {
                res += find(pos+1, cur)
            }

            return res
        }

        ans[i] = find(0, root)
    }

    return ans
}

javascript 解法, 执行用时: 272 ms, 内存消耗: 65.3 MB, 提交时间: 2023-09-22 10:27:30

/**
 * @param {string[]} words
 * @param {string[]} puzzles
 * @return {number[]}
 */
var findNumOfValidWords = function(words, puzzles) {
    const frequency = new Map();

    for (const word of words) {
        let mask = 0;
        for (const ch of word) {
            mask |= (1 << (ch.charCodeAt() - 'a'.charCodeAt()));
        }
        if (CountOne(mask) <= 7) {
            frequency.set(mask, (frequency.get(mask) || 0) + 1);
        }
    }

    const ans = [];
    for (const puzzle of puzzles) {
        let total = 0;

        // 枚举子集方法一
        // for (let choose = 0; choose < (1 << 6); ++choose) {
        //     let mask = 0;
        //     for (let i = 0; i < 6; ++i) {
        //         if (choose & (1 << i)) {
        //             mask |= (1 << (puzzle[i + 1].charCodeAt() - 'a'.charCodeAt()));
        //         }
        //     }
        //     mask |= (1 << (puzzle[0].charCodeAt() - 'a'.charCodeAt()));
        //     if (frequency.has(mask)) {
        //         total += frequency.get(mask);
        //     }
        // }
        // 枚举子集方法二
        let mask = 0;
        for (let i = 1; i < 7; ++i) {
            mask |= (1 << (puzzle[i].charCodeAt() - 'a'.charCodeAt()));
        }
        let subset = mask;
        while (subset) {
            let s = subset | (1 << (puzzle[0].charCodeAt() - 'a'.charCodeAt()));
            if (frequency.has(s)) {
                total += frequency.get(s);
            }
            subset = (subset - 1) & mask;
        }
        // 在枚举子集的过程中，要么会漏掉全集 mask，要么会漏掉空集
        // 这里会漏掉空集，因此需要额外判断空集
        if (frequency.has(1 << (puzzle[0].charCodeAt() - 'a'.charCodeAt()))) {
            total += frequency.get(1 << (puzzle[0].charCodeAt() - 'a'.charCodeAt()));
        }
        ans.push(total);
    }
    return ans;
};

function CountOne(n) {
    const str = n.toString(2);
    let count = 0;
    for (const ch of str) {
        if (parseInt(ch) === 1) {
            count++;
        }
    }
    return count;
}

java 解法, 执行用时: 90 ms, 内存消耗: 69.6 MB, 提交时间: 2023-09-22 10:27:14

class Solution {
    TrieNode root;

    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        root = new TrieNode();
        
        for (String word : words) {
            // 将 word 中的字母按照字典序排序并去重
            char[] arr = word.toCharArray();
            Arrays.sort(arr);
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < arr.length; ++i) {
                if (i == 0 || arr[i] != arr[i - 1]) {
                    sb.append(arr[i]);
                }
            }
            // 加入字典树中
            add(root, sb.toString());
        }

        List<Integer> ans = new ArrayList<Integer>();
        for (String puzzle : puzzles) {
            char required = puzzle.charAt(0);
            char[] arr = puzzle.toCharArray();
            Arrays.sort(arr);
            ans.add(find(new String(arr), required, root, 0));
        }
        return ans;
    }

    public void add(TrieNode root, String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); ++i) {
            char ch = word.charAt(i);
            if (cur.child[ch - 'a'] == null) {
                cur.child[ch - 'a'] = new TrieNode();
            }
            cur = cur.child[ch - 'a'];
        }
        ++cur.frequency;
    }

    // 在回溯的过程中枚举 puzzle 的所有子集并统计答案
    // find(puzzle, required, cur, pos) 表示 puzzle 的首字母为 required, 当前搜索到字典树上的 cur 节点，并且准备枚举 puzzle 的第 pos 个字母是否选择（放入子集中）
    // find 函数的返回值即为谜底的数量
    public int find(String puzzle, char required, TrieNode cur, int pos) {
        // 搜索到空节点，不合法，返回 0
        if (cur == null) {
            return 0;
        }
        // 整个 puzzle 搜索完毕，返回谜底的数量
        if (pos == 7) {
            return cur.frequency;
        }

        // 选择第 pos 个字母
        int ret = find(puzzle, required, cur.child[puzzle.charAt(pos) - 'a'], pos + 1);

        // 当 puzzle.charAt(pos) 不为首字母时，可以不选择第 pos 个字母
        if (puzzle.charAt(pos) != required) {
            ret += find(puzzle, required, cur, pos + 1);
        }

        return ret;
    }
}

class TrieNode {
    int frequency;
    TrieNode[] child;

    public TrieNode() {
        frequency = 0;
        child = new TrieNode[26];
    }
}

java 解法, 执行用时: 66 ms, 内存消耗: 69.8 MB, 提交时间: 2023-09-22 10:27:01

class Solution {
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        Map<Integer, Integer> frequency = new HashMap<Integer, Integer>();

        for (String word : words) {
            int mask = 0;
            for (int i = 0; i < word.length(); ++i) {
                char ch = word.charAt(i);
                mask |= (1 << (ch - 'a'));
            }
            if (Integer.bitCount(mask) <= 7) {
                frequency.put(mask, frequency.getOrDefault(mask, 0) + 1);
            }
        }

        List<Integer> ans = new ArrayList<Integer>();
        for (String puzzle : puzzles) {
            int total = 0;

            // 枚举子集方法一
            // for (int choose = 0; choose < (1 << 6); ++choose) {
            //     int mask = 0;
            //     for (int i = 0; i < 6; ++i) {
            //         if ((choose & (1 << i)) != 0) {
            //             mask |= (1 << (puzzle.charAt(i + 1) - 'a'));
            //         }
            //     }
            //     mask |= (1 << (puzzle.charAt(0) - 'a'));
            //     if (frequency.containsKey(mask)) {
            //         total += frequency.get(mask);
            //     }
            // }

            // 枚举子集方法二
            int mask = 0;
            for (int i = 1; i < 7; ++i) {
                mask |= (1 << (puzzle.charAt(i) - 'a'));
            }
            int subset = mask;
            do {
                int s = subset | (1 << (puzzle.charAt(0) - 'a'));
                if (frequency.containsKey(s)) {
                    total += frequency.get(s);
                }
                subset = (subset - 1) & mask;
            } while (subset != mask);
            
            ans.add(total);
        }
        return ans;
    }
}

cpp 解法, 执行用时: 292 ms, 内存消耗: 79.8 MB, 提交时间: 2023-09-22 10:25:48

struct TrieNode {
    int frequency = 0;
    TrieNode* child[26];

    TrieNode() {
        for (int i = 0; i < 26; ++i) {
            child[i] = nullptr;
        }
    }
};

class Solution {
private:
    TrieNode* root;

public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        root = new TrieNode();

        auto add = [&](const string& word) {
            TrieNode* cur = root;
            for (char ch: word) {
                if (!cur->child[ch - 'a']) {
                    cur->child[ch - 'a'] = new TrieNode();
                }
                cur = cur->child[ch - 'a'];
            }
            ++cur->frequency;
        };

        // 在回溯的过程中枚举 puzzle 的所有子集并统计答案
        // find(puzzle, required, cur, pos) 表示 puzzle 的首字母为 required, 当前搜索到字典树上的 cur 节点，并且准备枚举 puzzle 的第 pos 个字母是否选择（放入子集中）
        // find 函数的返回值即为谜底的数量
        function<int(const string&, char, TrieNode*, int)> find = [&](const string& puzzle, char required, TrieNode* cur, int pos) {
            // 搜索到空节点，不合法，返回 0
            if (!cur) {
                return 0;
            }
            // 整个 puzzle 搜索完毕，返回谜底的数量
            if (pos == 7) {
                return cur->frequency;
            }
            
            // 选择第 pos 个字母
            int ret = find(puzzle, required, cur->child[puzzle[pos] - 'a'], pos + 1);

            // 当 puzzle[pos] 不为首字母时，可以不选择第 pos 个字母
            if (puzzle[pos] != required) {
                ret += find(puzzle, required, cur, pos + 1);
            }
            
            return ret;
        };
        
        for (string word: words) {
            // 将 word 中的字母按照字典序排序并去重
            sort(word.begin(), word.end());
            word.erase(unique(word.begin(), word.end()), word.end());
            // 加入字典树中
            add(word);
        }

        vector<int> ans;
        for (string puzzle: puzzles) {
            char required = puzzle[0];
            sort(puzzle.begin(), puzzle.end());
            ans.push_back(find(puzzle, required, root, 0));
        }
        return ans;
    }
};

cpp 解法, 执行用时: 248 ms, 内存消耗: 67.9 MB, 提交时间: 2023-09-22 10:25:39

class Solution {
public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        unordered_map<int, int> frequency;

        for (const string& word: words) {
            int mask = 0;
            for (char ch: word) {
                mask |= (1 << (ch - 'a'));
            }
            if (__builtin_popcount(mask) <= 7) {
                ++frequency[mask];
            }
        }

        vector<int> ans;
        for (const string& puzzle: puzzles) {
            int total = 0;

            // 枚举子集方法一
            // for (int choose = 0; choose < (1 << 6); ++choose) {
            //     int mask = 0;
            //     for (int i = 0; i < 6; ++i) {
            //         if (choose & (1 << i)) {
            //             mask |= (1 << (puzzle[i + 1] - 'a'));
            //         }
            //     }
            //     mask |= (1 << (puzzle[0] - 'a'));
            //     if (frequency.count(mask)) {
            //         total += frequency[mask];
            //     }
            // }

            // 枚举子集方法二
            int mask = 0;
            for (int i = 1; i < 7; ++i) {
                mask |= (1 << (puzzle[i] - 'a'));
            }
            int subset = mask;
            do {
                int s = subset | (1 << (puzzle[0] - 'a'));
                if (frequency.count(s)) {
                    total += frequency[s];
                }
                subset = (subset - 1) & mask;
            } while (subset != mask);
            
            ans.push_back(total);
        }
        return ans;
    }
};

python3 解法, 执行用时: 1056 ms, 内存消耗: 40.3 MB, 提交时间: 2023-09-22 10:24:30

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        frequency = collections.Counter()

        for word in words:
            mask = 0
            for ch in word:
                mask |= (1 << (ord(ch) - ord("a")))
            if str(bin(mask)).count("1") <= 7:
                frequency[mask] += 1
        
        ans = list()
        for puzzle in puzzles:
            total = 0

            # 枚举子集方法一
            # for choose in range(1 << 6):
            #     mask = 0
            #     for i in range(6):
            #         if choose & (1 << i):
            #             mask |= (1 << (ord(puzzle[i + 1]) - ord("a")))
            #     mask |= (1 << (ord(puzzle[0]) - ord("a")))
            #     if mask in frequency:
            #         total += frequency[mask]

            # 枚举子集方法二
            mask = 0
            for i in range(1, 7):
                mask |= (1 << (ord(puzzle[i]) - ord("a")))
            
            subset = mask
            while subset:
                s = subset | (1 << (ord(puzzle[0]) - ord("a")))
                if s in frequency:
                    total += frequency[s]
                subset = (subset - 1) & mask
            
            # 在枚举子集的过程中，要么会漏掉全集 mask，要么会漏掉空集
            # 这里会漏掉空集，因此需要额外判断空集
            if (1 << (ord(puzzle[0]) - ord("a"))) in frequency:
                total += frequency[1 << (ord(puzzle[0]) - ord("a"))]

            ans.append(total)
        
        return ans
        


class TrieNode:
    def __init__(self):
        self.frequency = 0
        self.child = dict()

# 基于字典树的解法
class Solution2:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        root = TrieNode()

        def add(word: List[str]):
            cur = root
            for ch in word:
                idx = ord(ch) - ord("a")
                if idx not in cur.child:
                    cur.child[idx] = TrieNode()
                cur = cur.child[idx]
            cur.frequency += 1

        # 在回溯的过程中枚举 puzzle 的所有子集并统计答案
        # find(puzzle, required, cur, pos) 表示 puzzle 的首字母为 required, 当前搜索到字典树上的 cur 节点，并且准备枚举 puzzle 的第 pos 个字母是否选择（放入子集中）
        # find 函数的返回值即为谜底的数量
        def find(puzzle: List[str], required: str, cur: TrieNode, pos: int) -> int:
            # 搜索到空节点，不合法，返回 0
            if not cur:
                return 0
            # 整个 puzzle 搜索完毕，返回谜底的数量
            if pos == 7:
                return cur.frequency
            
            ret = 0
            # 选择第 pos 个字母
            if (idx := ord(puzzle[pos]) - ord("a")) in cur.child:
                ret += find(puzzle, required, cur.child[idx], pos + 1)

            # 当 puzzle[pos] 不为首字母时，可以不选择第 pos 个字母
            if puzzle[pos] != required:
                ret += find(puzzle, required, cur, pos + 1)
            
            return ret
        
        for word in words:
            # 将 word 中的字母按照字典序排序并去重
            word = sorted(set(word))
            # 加入字典树中
            add(word)

        ans = list()
        for puzzle in puzzles:
            required = puzzle[0]
            puzzle = sorted(puzzle)
            ans.append(find(puzzle, required, root, 0))
        
        return ans

java 解法, 执行用时: 79 ms, 内存消耗: 69.6 MB, 提交时间: 2023-09-22 10:22:49

class Solution {
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        Map<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> res = new ArrayList<>(puzzles.length);
        for (String p : puzzles) {
            char[] puzzle = p.toCharArray();
            res.add(dfs(puzzle, 1, map, 1 << puzzle[0] - 'a'));// 首字符必选
        }
        return res;
    }
    public int dfs(char[] puzzle, int idx, Map<Integer, Integer> map, int key) {
        if (idx == puzzle.length) return map.getOrDefault(key, 0);
        // 首字符之外的字符可选可不选，两种情况
        return dfs(puzzle, idx + 1, map, key) + dfs(puzzle, idx + 1, map, key | 1 << puzzle[idx] - 'a');
    }
}

python3 解法, 执行用时: 1528 ms, 内存消耗: 40.2 MB, 提交时间: 2023-09-22 10:22:20

# 状态压缩 + 子集
class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        freq = collections.Counter()
        for word in words:
            mask = 0
            for c in word:
                mask |= 1 << (ord(c) - ord('a'))
            freq[mask] += 1
        res = []
        for puzzle in puzzles:
            total = 0
            for perm in self.subsets(puzzle[1:]):
                mask = 1 << (ord(puzzle[0]) - ord('a'))
                for c in perm:
                    mask |= 1 << (ord(c) - ord('a'))
                total += freq[mask]
            res.append(total)
        return res
    
    def subsets(self, words: List[int]) -> List[List[int]]:
        res = ['']
        for i in words:
            res = res + [i + word for word in res]
        return res