LeetCode 748. 最短完整词

示例 1：
输入：licensePlate = "1s3 PSt", 
words = ["step", "steps", "stripe", "stepple"]
输出："steps"
说明：最短完整词应该包括 "s"、"p"、"s" 以及 "t"。
对于 "step" 它只包含一个 "s" 所以它不符合条件。
同时在匹配过程中我们忽略牌照中的大小写。
 
示例 2：
输入：licensePlate = "1s3 456", 
words = ["looks", "pest", "stew", "show"]
输出："pest"
说明：存在 3 个包含字母 "s" 且有着最短长度的完整词，
但我们返回最先出现的完整词。
 
注意:
牌照（licensePlate）的长度在区域[1, 7]中。
牌照（licensePlate）将会包含数字、空格、或者字母（大写和小写）。
单词列表（words）长度在区间 [10, 1000] 中。
每一个单词 words[i] 都是小写，并且长度在区间 [1, 15] 中。

class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        unordered_map<char,int> m;
        for(char c : licensePlate)
        	if(isalpha(c))
        		m[tolower(c)]++;//字符计数
        unordered_map<char,int> wc;
        int minLen = INT_MAX;
        bool flag;
        string ans;
        for(string word : words)
        {
        	wc.clear();
        	flag = true;
        	for(char c : word)
        		if(isalpha(c))
        			wc[c]++;//单词字符计数
        	for(auto lpChar : m)
        	{
        		if(wc.find(lpChar.first) == wc.end() || wc[lpChar.first] < lpChar.second)
        		{	//单词中没有这个牌照字符，或者不够
        			flag = false;
        			break;
        		}
        	}
        	if(flag)
        	{
        		if(word.size() < minLen)
        		{
        			minLen = word.size();
        			ans = word;
        		}
        	}
        }
        return ans;
    }
};