> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/601-800/748.-zui-duan-wan-zheng-ci.md).

# 748. 最短完整词

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

## 解法一：直方图法

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

```python
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])
```