748. 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:
licensePlate will be a string with length in range [1, 7].
licensePlate will contain digits, spaces, or letters (uppercase or lowercase).
words will have a length in the range [10, 1000].
Every words[i] will consist of lowercase letters, and have length in range [1, 15].

思路:(看讨论的,叫做直方图解法,特别巧妙)

class Solution {
    inline bool metLicense(vector<int> vec) {  //判断vec中是否存在>0的元素
        for (auto i : vec) {
            if (i > 0) 
                return false;  //细节:注意一定要>0, !=0都不行.
        }                      //因为题目要求的是plate里面出现的一定要满足,但不限制出现plate以外的字符.
        return true;
    }
public:
    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        string res;
        vector<int> dict(26);
        for (auto c : licensePlate) { //将plate出现的字符映射到dict数组的0~25号位置,
            if (isalpha(c)) //若是字符
                dict[tolower(c) - 'a']++;  //全部转为小写,检测到一个,相应位置就+1
        }
        for (auto s : words) {  //遍历每个string
            vector<int> tmp = dict; //tmp复制dict,用于检测
            for (auto c : s) {  //对string的每个字符
                if (isalpha(c)) tmp[tolower(c) - 'a']--;  //tmp相应位置-1
            }
            //借助辅助函数metLicense判断是否满足要求
            //此外若发现更短的串,或者是初始串的时候
            if (metLicense(tmp) && (s.length() < res.length() || res.length() == 0))
                res = s;
        }
        return res;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 13,442评论 0 23
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,349评论 0 33
  • 上帝之眼,看见自己,看见别人! 不行动,无改变!
    风清杨阅读 1,189评论 0 1
  • 看左看右,是谁与你结伴同行?向前向后,又是谁在阻你前进? 若人生是绽放的花蕾,你是万般呵护下的花蕊,雍容华贵,熠熠...
    乔巧一汀阅读 1,254评论 2 3
  • 回到家,又被臭骂,看来今天是没心情写字了。 不能把工作带到家里来,和家长微信沟通。孩子爹闹意见,没人陪他。 哎,今...
    我是慕一阅读 871评论 0 0