【leetcode】1178. Number of Valid Words for Each Puzzle

题目如下：

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.

解题思路：本题可以采用逆向思维法。首先把words中的每个单词都做去掉重复字符处理，然后按字典序重新把字符排序，得到新的单词，例如 ealebb 经过处理后就是 able。接下来对puzzles中的每个单词除第一个字符外的子字符串做同样的处理，例如 gawbxyz 处理后的结果是 g + abwxyz 两部分。对于满足gawbxyz谜底的单词要具备的条件是第一个字符g是必定存在，同时后面的abwxyz 任意选择0~6个字符，这要判断这些组合有哪些在处理words中出现过，即可得puzzles中每个puzzle的结果。因为puzzles[i].length == 7，所以最多只会有2^6次方中组合，不会存在性能问题。

代码如下：

class Solution(object):
    def findNumOfValidWords(self, words, puzzles):
        """
        :type words: List[str]
        :type puzzles: List[str]
        :rtype: List[int]
        """
        dic_words = {}
        for word in words:
            newword = ''.join(sorted(list(set(list(word)))))
            dic_words[newword] = dic_words.setdefault(newword,0) + 1
        res = []
        for puzzle in puzzles:
            count = 0
            first = puzzle[0]
            puzzle = ''.join(sorted(list(set(list(puzzle[1:])))))
            if puzzle.find(first) != -1:
                inx = puzzle.find(first)
                puzzle = puzzle[:inx] + puzzle[inx+1:]
            if first in dic_words:
                count += dic_words[first]
            queue = []
            for (i,v) in enumerate(puzzle):
                queue.append((v,i))
            while len(queue) > 0:
                v,i = queue.pop(0)
                if i == len(puzzle) - 1:
                    key = ''.join(sorted(list(first + v)))
                    if key in dic_words:
                        count += dic_words[key]
                    continue
                queue.append((v,i+1))
                queue.append((v + puzzle[i+1],i+1))
            res.append(count)
        return res