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 <= 7licensePlatecontains digits, letters (uppercase or lowercase), or space' '.1 <= words.length <= 10001 <= words[i].length <= 15words[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;
}
}
Input
Output
#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))]
}
Input
Output
#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]
Input
Output
#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;
}
}
}
Input
Output