[LeetCode] Shortest Completing Word

Find the minimum length word from a given dictionary words, which has all the letters from the string licensePlate. Such a word is said to complete the given string licensePlate

Here, for letters we ignore case. For example, "P" on the licensePlate still matches "p" on the word.

It is guaranteed an answer exists. If there are multiple answers, return the one that occurs first in the array.

The license plate might have the same letter occurring multiple times. For example, given a licensePlate of "PP", the word "pair"does not complete the licensePlate, but the word "supper" does.

Example 1:

Input: licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
Output: "steps"
Explanation: The smallest length word that contains the letters "S", "P", "S", and "T".
Note that the answer is not "step", because the letter "s" must occur in the word twice.
Also note that we ignored case for the purposes of comparing whether a letter exists in the word.

Example 2:

Input: licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]
Output: "pest"
Explanation: There are 3 smallest length words that contains the letters "s".
We return the one that occurred first.

Note:

1. licensePlate will be a string with length in range [1, 7].
2. licensePlate will contain digits, spaces, or letters (uppercase or lowercase).
3. words will have a length in the range [10, 1000].
4. Every words[i] will consist of lowercase letters, and have length in range [1, 15].

题目有点绕，但是明白题意之后条理很清楚。

就是给定一个字符串和一个字符串数组，找出字符串中字母与字符串数组中最匹配的那个最短字符串，如果最短字符串存在多个，则返回第一个出现的字符串。

这个给定的字符串中包括空格、数字、大小写字母以及标点。

首先先将字符串中的字母字符都转换成小写字母并使用map统计其出现的次数。

然后遍历字符串数组，这里维护一个map的副本、一个字符串数组中字符串最小长度一个与字符串数组中字符串的最大匹配数。

当存在最大匹配数相同时判断字符串长度，取较小长度的字符串并维护这个最小长度。

当存在匹配数大于当前匹配数时，维护当前最大匹配数以及这个匹配字符串的长度作为最小长度。更新匹配字符串。

class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        unordered_map<char, int> m;
        unordered_map<char, int> tmp;
        for (auto c : licensePlate) {
            if (isalpha(c))
                m[tolower(c)]++;
        }
        string res = "";
        int maxCnt = INT_MIN;
        int minSize = INT_MAX;
        for (auto word : words) {
            int cnt = 0;
            tmp = m;
            int n = word.size();
            for (int i = 0; i < n; i++) {
                if (tmp.count(word[i]) > 0) {
                    cnt++;
                    tmp[word[i]]--;
                    if (tmp[word[i]] == 0)
                        tmp.erase(word[i]);
                }
            }
            if (cnt == maxCnt) {
                if (n < minSize) {
                    minSize = n;
                    res = word;
                }
            }
            else if (cnt > maxCnt) {
                maxCnt = cnt;
                minSize = n;
                res = word;
            }
        }
        return res;      
    }
};
// 22 ms