Problem: 748. Shortest Completing Word 最短补全词
解题过程
耗时100%，放入字符串和索引，然后根据长度、索引排序，最后统计字符数量，判断是否满足条件，满足即可返回。哈希表unordered_map速度比较慢，直接用的26长度的数组
Code
class Solution { public: int ump[26], tmp[26]; string shortestCompletingWord(string licensePlate, vector<string>& words) { vector<pair<string, int>> tr; for(int i = 0; i < words.size(); i++) { tr.push_back({words[i], i}); } sort(tr.begin(), tr.end(), [&](pair<string, int>&a, pair<string, int>&c) { if(a.first.size()==c.first.size()) return a.second < c.second; else return a.first.size() < c.first.size(); }); memset(ump, 0, sizeof(ump)); // unordered_map<char, int> ump; for(char& c:licensePlate) { if(c>='A' && c<='Z') ump[(c-'A')]++; else if(c>='a' && c<='z') ump[c-'a']++; } // unordered_map<char, int>::iterator it; for(int i = 0; i < tr.size(); i++) { // unordered_map<char, int> tmp; memset(tmp, 0, sizeof(tmp)); for(char& c : tr[i].first) { tmp[c-'a']++; } bool find = true; for(int i = 0; i < 26; i++) { if(tmp[i] < ump[i]) { find = false; break; } } // for(it = ump.begin(); it!=ump.end(); it++) { // if(tmp.find(it->first)==tmp.end() || tmp[it->first] < it->second) { // find = false; // break; // } // } if(find) return tr[i].first; } return ""; } };
