1178

1178. Number of Valid Words for Each Puzzle (Hard)

With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:

• word contains the first letter of puzzle.
• For each letter in word, that letter is in puzzle.
  • For example, if the puzzle is "abcdefg", then valid words are "faced", "cabbage", and "baggage", while
  • invalid words are "beefed" (does not include 'a') and "based" (includes 's' which is not in the puzzle).

Return an array answer, where answer[i] is the number of words in the given word list words that is valid with respect to the puzzle puzzles[i].

 

Example 1:

Input: words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
Output: [1,1,3,2,4,0]
Explanation: 
1 valid word for "aboveyz" : "aaaa" 
1 valid word for "abrodyz" : "aaaa"
3 valid words for "abslute" : "aaaa", "asas", "able"
2 valid words for "absoryz" : "aaaa", "asas"
4 valid words for "actresz" : "aaaa", "asas", "actt", "access"
There are no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.

Example 2:

Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0,1,3,2,0]

 

Constraints:

• 1 <= words.length <= 105
• 4 <= words[i].length <= 50
• 1 <= puzzles.length <= 104
• puzzles[i].length == 7
• words[i] and puzzles[i] consist of lowercase English letters.
• Each puzzles[i] does not contain repeated characters.

Companies:
Dropbox

Related Topics:
Array, Hash Table, String, Bit Manipulation, Trie

Solution 1. Bitmask

The key is to realize that there are at most 2^6 = 64 bitmasks for each puzzle.

// OJ: https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/
// Author: github.com/lzl124631x
// Time: O(WC + P * 2^L) where `W` is the length of `words`, `C` is the max length of `words[i]`, `P` is the length of `puzzles`, and `L` is the length of `puzzles[i]`.
// Space: O(W)
class Solution {
public:
    vector<int> findNumOfValidWords(vector<string>& W, vector<string>& P) {
        unordered_map<int, int> cnt;
        for (auto &s : W) {
            int m = 0;
            for (char c : s) m |= 1 << (c - 'a');
            if (__builtin_popcount(m) > 7) continue;
            cnt[m]++;
        }
        function<int(string&, int, int)> dfs = [&](string &s, int i, int m) {
            if (i == s.size()) return cnt.count(m) ? cnt[m] : 0;
            return dfs(s, i + 1, m) + dfs(s, i + 1, m | (1 << (s[i] - 'a')));
        };
        vector<int> ans;
        for (auto &s : P) {
            int m = 1 << (s[0] - 'a');
            ans.push_back(dfs(s, 1, m));
        }
        return ans;
    }
};

Or

// OJ: https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/
// Author: github.com/lzl124631x
// Time: O(WC + P * 2^L) where `W` is the length of `words`, `C` is the max length of `words[i]`, `P` is the length of `puzzles`, and `L` is the length of `puzzles[i]`.
// Space: O(W)
class Solution {
    int encode(const string &s) {
        int b = 0;
        for (char c : s) b |= 1 << (c - 'a');
        return b;
    }
public:
    vector<int> findNumOfValidWords(vector<string>& W, vector<string>& P) {
        unordered_map<int, int> cnt;
        for (auto &w : W) cnt[encode(w)]++;
        vector<int> ans;
        auto count = [&](int m) { return cnt.count(m) ? cnt[m] : 0; };
        for (auto &p : P) {
            int b = encode(p.substr(1)), first = 1 << (p[0] - 'a'), c = count(first);
            for (int m = b; m; m = (m - 1) & b) c += count(m | first);
            ans.push_back(c);
        }
        return ans;
    }
};

Solution 2. Trie

// OJ: https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/
// Author: github.com/lzl124631x
// Time: O(WC + P * 2^L) where `W` is the length of `words`, `C` is the max length of `words[i]`, `P` is the length of `puzzles`, and `L` is the length of `puzzles[i]`.
// Space: O(W)
struct TrieNode {
    TrieNode *next[26] = {};
    int cnt = 0;
};
class Solution {
    int encode(const string &s) {
        int b = 0;
        for (char c : s) b |= 1 << (c - 'a');
        return b;
    }
    void addWord(TrieNode *node, int b) {
        if (__builtin_popcount(b) > 7) return;
        for (int i = 0; i < 26; ++i) {
            if ((b >> i & 1) == 0) continue;
            if (!node->next[i]) node->next[i] = new TrieNode();
            node = node->next[i];
        }
        node->cnt++;
    }
    int dfs(TrieNode *node, int b, int i, int first) {
        if (!node) return 0;
        if (i == 26) return node->cnt;
        if (i == first) return dfs(node->next[i], b, i + 1, first); // first letter must be selected.
        if ((b >> i & 1) == 0) return dfs(node, b, i + 1, first); // this letter is not in the puzzle, skip
        return dfs(node->next[i], b, i + 1, first) + dfs(node, b, i + 1, first); // either choose the current letter or not
    }
public:
    vector<int> findNumOfValidWords(vector<string>& W, vector<string>& P) {
        TrieNode root;
        for (auto &w : W) addWord(&root, encode(w));
        vector<int> ans;
        for (auto &p : P) ans.push_back(dfs(&root, encode(p.substr(1)), 0, p[0] - 'a'));
        return ans;
    }
};