748. 最短完整词

https://leetcode-cn.com/problems/shortest-completing-word/

解法一：直方图法

用一个dict[26]数组统计plate中26个字符出现的频率。检测words中每个串，遇到某个字符就将dict相应字符频率-1。因为题目要求的是plate里面出现的一定要满足,但不限制出现plate以外的字符，所以只有当dict所有元素为0（满足plate），或者小于0，该串才符合题意。

class Solution:
    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
        res = ''
        dict = [0] * 26
        #建立字典
        for ch in licensePlate:
            if ch.isalpha():
                dict[ord(ch.lower()) - 97] += 1
                
        for word in words:
            tmp = list(dict)    #复制一份用于检测
            for ch in word:
                tmp[ord(ch.lower()) - 97] -= 1
            #符合plate，并且长度最小
            if self.metLicense(tmp) and (len(word) < len(res) or res == ''):
                res = word
        return res
        
    #辅助函数，只要数组中有一个>0元素，返回false
    def metLicense(self, nums):
        return not any([x>0 for x in nums])