Generate longest word

given a bag of chars, and a dictionary contains with many words, find list of maximum length word which can be generated from the bag of chars respectively. 字符集中的字符不一定全用上。

bag may contain duplicate characters.The char in bag cannot be reused. bag {a,p,l,e} cannot generate word 'apple'.

case 2: bag of chars

{'a', 'p', 'p', 'l', 'e', 'o'}

dict

{'apple', 'people'}

return

{'apple'}

because people need 2 char 'e', there is only 1 'e' in the bag.

思路：我觉得这道题用trie不好写。

因为你用单词来build trie的话。相当于你要用bag of chars去dfs每一个trie的path。然后一个一个char的删除，直到hit到word最后一个字母，或者节点不在bag里面。如果能hit到word最后一个字母，记录这个word,和深度。最后比较所有能dfs出来的word的长度。感觉不是很酷炫。

这个我们提供一个更酷炫的思路。你不是要保证你的单词所有字母在bag里面么，本宝宝直接用一个counter来存你的bag。key是字母，value是有多少个。然后我把每一个word都做成couter，直接并集。如果bag的counter不变的话，那么说明这个word就被bag给包括了。最后直接存最长那个就行了。

举例Counter object是怎么回事

bag = ['a','a','b','r'] 
counter = {'a':2, 'b':1, 'r':1}

代码如下：

import collections
class Solution(object):
    def findLongest(self, bag, words):
        """
        :type bag: List[char]
        :type words: List[str]
        :rtype: str
        """
        d = collections.Counter(bag)
        res = []
        for w in words:
            tmp = collections.Counter(w)
            if d == (d|tmp):
                if not res:
                    res.append(w)
                else:
                    if len(set(w))>len(set(res[0])):
                        res = [w]
                    elif len(set(w))==len(set(res[0])):
                        res.append(w)
        return res

bag = ['u','b','e','r','d']
words = ['uber', 'red']

so = Solution()
ans = so.findLongest(bag, words)
print(ans)

bag = ['a','p','p','l','e','o']
words = {'apple', 'people'}
ans = so.findLongest(bag, words)
print(ans)

bag = ['i','n','b','o','x','d','r','a','f','t','m','r','e']
words = {'inbox', 'draft', 'more'}
ans = so.findLongest(bag, words)
print(ans)