[leetcode #1178] Number of Valid Words for Each Puzzle

Problem

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 <= 10⁵
・ 4 <= words[i].length <= 50
・ 1 <= puzzles.length <= 10⁴
・ puzzles[i].length == 7
・ words[i] and puzzles[i] consist of lowercase English letters.
・ Each puzzles[i] does not contain repeated characters.

Idea

오랜만에 난이도 Hard인 문제가 나왔다.

주어진 Puzzle array의 string에서 valid한 words가 각각 몇 개인지 확인하는 문제다. Valid인 word는 puzzle의 첫 번째 문자를 포함해야하며, word의 모든 문자가 puzzle에 있는 문자여야 한다.

Brute-force로 풀면 Time Limit Exceeded에 걸릴 게 뻔하다. words와 puzzle의 길이는 짧지만 words의 개수가 최대 100,000개, puzzle의 개수가 최대 10,000개나 되기 때문이다.

Valid한 문자열을 찾기 위해선 제약 조건에 주의해야 한다. 문자의 중복 여부와 상관없이 puzzle에 있는 문자만 가지고 있으면 조건을 충족하므로 bitmask 연산을 통해 각 string을 변환할 수 있다. 그리고 똑같은 형태의 bitmask 값을 반복해서 찾지 않기 위해 map을 사용한다.

또 다른 조건인 puzzle의 첫 번째 문자를 반드시 포함해야 하는 조건 또한 bitmask 연산으로 해결할 수 있다. 각 puzzle을 탐색하면서 puzzle의 첫 번째 문자를 bitmask로 저장한 뒤, 해당 값이 map에 있으면 count를 늘린다. 이 때 사용한 bitmask 값은 추후에 puzzle의 문자를 포함하는 문자열을 찾기 위해 사용된다.

다음으로 puzzle에서 첫 번째 문자를 제외한 substring의 bitmask 값 (= submask)을 구한다. substing을 bitmask로 한 값에 첫 번째 문자의 bitmask 값을 OR 연산시키면 Valid한 문자열의 bitmask 값이 나오게 된다. 해당 값이 map에 있는지 확인하고 있으면 count값을 늘린다.

이후에 Valid한 문자열의 bitmask값은 submask에서 1을 뺀 뒤 mask와 AND 연산을 통해 구할 수 있다. AND 연산을 통해 puzzle이 포함하지 않은 bit는 자동으로 제외되기 때문이다. puzzle에서 valid한 문자열의 bitmask를 전부 탐색한 뒤 계산한 값을 결과로 리턴할 list에 더한다.

알파벳이 26개밖에 되지 않기 때문에 총 32개의 bit를 가지고 있는 int에 저장할 수 있다. 중복 여부와 상관없이 puzzle의 문자를 활용하기만 하면 되므로 문자열을 bit로 변환할 수 있는 특징을 잘 활용해야 하는 문제였다.

Solution

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

        for (int i=0; i < words.length; i++) {
            int mask = bitMask(words[i]);

            bitMaskOfWordsMap.put(mask, bitMaskOfWordsMap.getOrDefault(mask, 0)+1);
        }

        List<Integer> res = new ArrayList<>();
        for (int i=0; i < puzzles.length; i++) {
            String puzzle = puzzles[i];
            int firstMask = 1 << (puzzle.charAt(0) - 'a');

            int count = bitMaskOfWordsMap.getOrDefault(firstMask, 0);

            int mask = bitMask(puzzle.substring(1));
            for (int subMask=mask; subMask > 0; subMask=(subMask-1) & mask) {
                count += bitMaskOfWordsMap.getOrDefault(subMask | firstMask, 0);
            }

            res.add(count);
        }

        return res;
    }

    private int bitMask(String word) {
        int res = 0;

        for (int i=0; i < word.length(); i++) {
            res |= (1 << word.charAt(i) - 'a');    
        }

        return res;
    }
}

Reference

https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/