題目鏈接：https://leetcode-cn.com/problems/shortest-completing-word/

題解匯總：https://leetcode-cn.com/problems/max-increase-to-keep-city-skyline/

---

題目描述

給你一個字符串 licensePlate 和一個字符串數組 words ，請你找出并返回 words 中的 最短補全詞 。

補全詞 是一個包含 licensePlate 中所有字母的單詞。

在匹配 licensePlate 中的字母時：

忽略 licensePlate 中的 數字和空格 。
不區分大小寫。
如果某個字母在 licensePlate 中出現不止一次，那么該字母在補全詞中的出現次數應當一致或者更多。
例如：licensePlate = “aBc 12c”，那么它的補全詞應當包含字母 ‘a’、‘b’ （忽略大寫）和兩個 ‘c’ 。可能的 補全詞 有 “abccdef”、“caaacab” 以及 “cbca” 。

請你找出并返回 words 中的 最短補全詞 。題目數據保證一定存在一個最短補全詞。當有多個單詞都符合最短補全詞的匹配條件時取 words 中 第一個 出現的那個。

示例 1：
輸入：licensePlate = “1s3 PSt”, words = [“step”, “steps”, “stripe”, “stepple”]
輸出：“steps”
解釋：最短補全詞應該包括 “s”、“p”、“s”（忽略大小寫） 以及 “t”。
“step” 包含 “t”、“p”，但只包含一個 “s”，所以它不符合條件。
“steps” 包含 “t”、“p” 和兩個 “s”。
“stripe” 缺一個 “s”。
“stepple” 缺一個 “s”。
因此，“steps” 是唯一一個包含所有字母的單詞，也是本例的答案。

示例 2：
輸入：licensePlate = “1s3 456”, words = [“looks”, “pest”, “stew”, “show”]
輸出：“pest”
解釋：licensePlate 只包含字母 “s” 。所有的單詞都包含字母 “s” ，其中 “pest”、“stew”、和 “show” 三者最短。答案是 “pest” ，因為它是三個單詞中在 words 里最靠前的那個。

示例 3：
輸入：licensePlate = “Ah71752”, words = [“suggest”,“letter”,“of”,“husband”,“easy”,“education”,“drug”,“prevent”,“writer”,“old”]
輸出：“husband”

示例 4：
輸入：licensePlate = “OgEu755”, words = [“enough”,“these”,“play”,“wide”,“wonder”,“box”,“arrive”,“money”,“tax”,“thus”]
輸出：“enough”

示例 5：
輸入：licensePlate = “iMSlpe4”, words = [“claim”,“consumer”,“student”,“camera”,“public”,“never”,“wonder”,“simple”,“thought”,“use”]
輸出：“simple”

---

簡單的模擬， 用hashmap記錄次數，比較即可

class Solution { public:string shortestCompletingWord(string licensePlate, vector<string>& words) {int resLen = 0x3fffffff;string res;unordered_map<char, int>sourse, target;for (auto i : licensePlate) {if (isalpha(i)) {sourse[tolower(i)]++;}}for (auto s : words) {target.clear();for (int i = 0; i < s.size(); i++) {target[s[i]]++;}for (auto u : sourse) {if (u.second > target[u.first]) goto loop;}if (s.size() < resLen) {resLen = s.size();res = s;}loop:;}return res;} };

總結

以上是生活随笔為你收集整理的【解题报告】Leecode 748. 最短补全词——Leecode每日一题系列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。