consists of lower case English letters.

Solution

Method 1 – Hash Counting

Intuition

We need to check for each word if it contains all the required letters (with counts) from the license plate. By counting the frequency of each letter in the license plate and each word, we can efficiently check if a word is a completing word.

Approach

Count the frequency of each letter (case-insensitive) in the license plate, ignoring digits and spaces.
For each word in the list:
- Count the frequency of each letter in the word.
- Check if the word contains at least as many of each required letter as in the license plate.
- If so, and the word is shorter than the current answer, update the answer.
Return the first shortest completing word found.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    string shortestCompletingWord(string licensePlate, vector<string>& words) {\n        vector<int> cnt(26);\n        for (char c : licensePlate) {\n            if (isalpha(c)) cnt[tolower(c) - 'a']++;\n        }\n        string ans;\n        for (const string& w : words) {\n            vector<int> wc(26);\n            for (char c : w) wc[c - 'a']++;\n            bool ok = true;\n            for (int i = 0; i < 26; ++i) {\n                if (cnt[i] > wc[i]) { ok = false; break; }\n            }\n            if (ok && (ans.empty() || w.size() < ans.size())) ans = w;\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">    string</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> shortestCompletingWord</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">string</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> licensePlate</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">string</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> words</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">        vector</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;int></span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> cnt</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\">26</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">);</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        for</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> (</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">char</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> c : licensePlate) {</span></span>\n<

Related Tags