## Algorithm

Problem Name: 748. Shortest Completing Word

Given a string `licensePlate` and an array of strings `words`, find the shortest completing word in `words`.

A completing word is a word that contains all the letters in `licensePlate`. Ignore numbers and spaces in `licensePlate`, and treat letters as case insensitive. If a letter appears more than once in `licensePlate`, then it must appear in the word the same number of times or more.

For example, if `licensePlate`` = "aBc 12c"`, then it contains letters `'a'`, `'b'` (ignoring case), and `'c'` twice. Possible completing words are `"abccdef"`, `"caaacab"`, and `"cbca"`.

Return the shortest completing word in `words`. It is guaranteed an answer exists. If there are multiple shortest completing words, return the first one that occurs in `words`.

Example 1:

```Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"
Explanation: licensePlate contains letters 's', 'p', 's' (ignoring case), and 't'.
"step" contains 't' and 'p', but only contains 1 's'.
"steps" contains 't', 'p', and both 's' characters.
"stripe" is missing an 's'.
"stepple" is missing an 's'.
Since "steps" is the only word containing all the letters, that is the answer.
```

Example 2:

```Input: licensePlate = "1s3 456", words = ["looks","pest","stew","show"]
Output: "pest"
Explanation: licensePlate only contains the letter 's'. All the words contain 's', but among these "pest", "stew", and "show" are shortest. The answer is "pest" because it is the word that appears earliest of the 3.
```

Constraints:

• `1 <= licensePlate.length <= 7`
• `licensePlate` contains digits, letters (uppercase or lowercase), or space `' '`.
• `1 <= words.length <= 1000`
• `1 <= words[i].length <= 15`
• `words[i]` consists of lower case English letters.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public String shortestCompletingWord(String licensePlate, String[] words) {
int shortestWordIdx = -1;
Map < Character, Integer> licensePlateFrequency = getFrequencyMap(licensePlate);
for (int i = 0; i  <  words.length; i++) {
if (canComplete(licensePlateFrequency, words[i])) {
if (shortestWordIdx == -1 || words[i].length() < words[shortestWordIdx].length()) {
shortestWordIdx = i;
}
}
}
return words[shortestWordIdx];
}

private boolean canComplete(Map < Character, Integer> licensePlateFrequency, String word) {
Map wordFrequency = getFrequencyMap(word);
for (Character key : licensePlateFrequency.keySet()) {
if (wordFrequency.getOrDefault(key, 0) < licensePlateFrequency.get(key)) {
return false;
}
}
return true;
}

private Map < Character, Integer> getFrequencyMap(String s) {
Map map = new HashMap<>();
for (char c : s.toCharArray()) {
if (Character.isLetter(c)) {
map.put(Character.toLowerCase(c), map.getOrDefault(Character.toLowerCase(c), 0) + 1);
}
}
return map;
}
}
``````
Copy The Code &

Input

cmd
licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]

Output

cmd
"steps"

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const shortestCompletingWord = function(licensePlate, words) {
const letters = licensePlate
.replace(/\d/g, '')
.replace(/ /g, '')
.toLowerCase()
.split('')
let matchingWords = words.filter(word => {
let completingWord = true
letters.forEach(letter => {
let letterIndex = word.indexOf(letter)
if (letterIndex > -1) {
let re = new RegExp(letter)
word = word.replace(re, '')
} else {
completingWord = false
}
})
return completingWord
})
const wordLengths = matchingWords.map(word => word.length)
return matchingWords[wordLengths.indexOf(Math.min.apply(Math, wordLengths))]
}
``````
Copy The Code &

Input

cmd
licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]

Output

cmd
"steps"

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def shortestCompletingWord(self, lp, words):
cntr_lp, res = {k: v for k, v in collections.Counter(lp.lower()).items() if k.isalpha()}, [None, None]
for word in words:
check = collections.Counter(word.lower())
if all(True if k in check and v <= check[k] else False for k, v in cntr_lp.items()):
if not any(res) or len(word) < res[1]: res = [word, len(word)]
return res[0]
``````
Copy The Code &

Input

cmd
licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]

Output

cmd
"steps"

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0748_ShortestCompletingWord
{
public string ShortestCompletingWord(string licensePlate, string[] words)
{
var target = CountWord(licensePlate.ToLower());
var result = string.Empty;
foreach (var word in words)
{
if (word.Length  <  result.Length || result.Length == 0)
{
var current = CountWord(word);
var match = true;
for (int i = 0; i  <  26; i++)
{
if (current[i] < target[i])
{
match = false;
break;
}
}

if (match)
result = word;
}
}

return result;
}

private int[] CountWord(string word)
{
var count = new int[26];
foreach (var ch in word)
if (char.IsLetter(ch)) count[ch - 'a']++;

return count;
}
}
}
``````
Copy The Code &

Input

cmd
licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]

Output

cmd
"steps"