[LeetCode/리트코드] #1178. Number of Valid Words for Each Puzzle[파이썬(python)/Bitmask/비트마스크]

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

Number of Valid Words for Each Puzzle - LeetCode

처음에는 문자열 문제인 줄 알고 쉬운 문제라고 생각하고 풀었으나

응 바로 시간초과 ^__^

 

 

시간초과 난 코드

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        arr=[0]*len(puzzles)
        idx=0
        for p in puzzles:
            for w in words:
                if p[0] not in w:
                    continue
                flag=0
                for i in range(len(w)):
                    if w[i] not in p:
                        flag=1
                        break
                if flag==0:
                    arr[idx]+=1   
            idx+=1
        return arr

 

알고보니 비트마스크 문제였다

비트마스크 문제였으니 당연히 시간초과가 날 수 밖에...ㅎㅎ

 

비트마스크는 0과 1로 마스킹하는 개념으로.. 시간복잡도 면에서는 굉장히 빠르다.

https://hidemasa.tistory.com/166

[자료구조] 비트마스크(BitMask) 알고리즘

트라이로도 풀 수 있는 문제였는데, 문자열 전용 트리라고 보면 된다.

트라이 자료구조를 언젠가 공부해서 다뤄보기로 했는데 미루고 미루다가 

얼른 공부하라는 뜻인지 오늘 리트코드 문제로 나왔네 ^^;;

 

리트코드에서 제시한 솔루션 코드는 각각 이렇다.

 

각 단어(words)를 비트마스킹한 후에 puzzles에 대하여 유효한 words를 카운트한다. 

 

 

비트마스크 풀이

 

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:

        def bitmask(word: str) -> int:
            mask = 0
            for letter in word:
                mask |= 1 << (ord(letter) - ord('a'))
            return mask

        # Create a bitmask for each word.
        word_count = Counter(bitmask(word) for word in words)

        result = []
        for puzzle in puzzles:
            first = 1 << (ord(puzzle[0]) - ord('a'))
            count = word_count[first]

            # Make bitmask but ignore the first character since it must always
            # be there.
            mask = bitmask(puzzle[1:])

            # Iterate over every possible subset of characters.
            submask = mask
            while submask:
                # Increment the count by the number of words that match the
                # current submask.
                count += word_count[submask | first]  # add first character
                submask = (submask - 1) & mask
            result.append(count)
        return result

 

트라이 풀이

 

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        SIZE = 26  # 26 letters in the alphabet
        trie = [[0] * SIZE]  # we use list to mimic the trie tree
        count = [0]  # the number of words ending at node i
        for word in words:
            word = sorted(set(word))
            if len(word) <= 7:  # longer words are never valid
                # insert into trie
                node = 0
                for letter in word:
                    i = ord(letter) - ord('a')
                    if trie[node][i] == 0:  # push empty node
                        trie.append([0] * SIZE)
                        count.append(0)
                        trie[node][i] = len(trie) - 1
                    node = trie[node][i]
                count[node] += 1

        # search for valid words
        def dfs(node, has_first):
            total = count[node] if has_first else 0
            for letter in puzzle:  # catch puzzle from outside environment
                i = ord(letter) - ord('a')
                if trie[node][i]:
                    total += dfs(trie[node][i], has_first or letter == puzzle[0])
            return total

        result = []
        for puzzle in puzzles:
            result.append(dfs(0, False))
        return result

트라이 자료구조를 자세히 공부해보면서 이 문제와 코드도 다시 한번 찬찬히 살펴봐야겠다.