Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1178.html

1178. Number of Valid Words for Each Puzzle

Level

Hard

Description

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” (doesn’t include “a”) and “based” (includes “s” which isn’t in the puzzle).

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

Example:

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’re no valid words for “gaswxyz” cause none of the words in the list contains letter ‘g’.

Constraints:

  • 1 <= words.length <= 10^5
  • 4 <= words[i].length <= 50
  • 1 <= puzzles.length <= 10^4
  • puzzles[i].length == 7
  • words[i][j], puzzles[i][j] are English lowercase letters.
  • Each puzzles[i] doesn’t contain repeated characters.

Solution

Use bitwise operation. Since there are at most 26 different lowercase letters, each string can be represented as an integer using bitwise operation. For example, if ‘a’ is in the string, add 1 to the integer. If ‘b’ is in the string, add 2 to the integer. If ‘c’ is in the string, add 4 to the integer. For each letter, only consider whether it exists in the string, and the number of occurrences of each letter is not considered.

Calculate bitwise representation for all words in words, and use a map to store each bitwise representation’s count. Then loop over puzzles. For each puzzle in puzzles, calculate bitwise representation of puzzle, and consider all the subsets of puzzle and calculate the count accordingly.

  • class Solution {
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        List<Integer> validCounts = new ArrayList<Integer>();
        Map<Integer, Integer> wordCountMap = new HashMap<Integer, Integer>();
        int puzzlesLength = puzzles.length;
        for (String word : words) {
            int bits = 0;
            int length = word.length();
            for (int i = 0; i < length; i++) {
                char c = word.charAt(i);
                bits |= 1 << c - 'a';
            }
            int count = wordCountMap.getOrDefault(bits, 0) + 1;
            wordCountMap.put(bits, count);
        }
        for (int i = 0; i < puzzlesLength; i++) {
            int wordsCount = 0;
            int bits = 0;
            String puzzle = puzzles[i];
            int length = puzzle.length();
            for (int j = 0; j < length; j++) {
                char c = puzzle.charAt(j);
                bits |= 1 << c - 'a';
            }
            char c0 = puzzle.charAt(0);
            for (int j = bits; j > 0; j = (j - 1) & bits) {
                if (((1 << c0 - 'a') & j) > 0)
                    wordsCount += wordCountMap.getOrDefault(j, 0);
            }
            validCounts.add(wordsCount);
        }
        return validCounts;
    }
}

All Problems

All Solutions