Java Solution Using HashMap (37 ms)

• ``````class Solution {
public String shortestCompletingWord(String licensePlate, String[] words) {
Map<Integer, Integer> licensePlateMap = new HashMap<>();
sortWordsLength(words);
}

// GIVEN: the letter frequency HashMap of the licensePlate, an words dictionary
// RETURNS: the minimum length word from words, which has all the letters in the HashMap
public String getShortestCompletingWord(Map<Integer, Integer> licensePlateMap, String[] words) {
String result = "";
for (String word : words) {
Map<Integer, Integer> wordMap = new HashMap<>();
enterWordToMap(word, wordMap);
boolean isComplete = true;
for (Integer i : licensePlateMap.keySet()) {
if (wordMap.get(i) == null || wordMap.get(i) < licensePlateMap.get(i)) {
isComplete = false;
break;
}
}
if (isComplete) {
return word;
}
}
return result;
}

// EFFECT: Sort the words array based on length of each word
public void sortWordsLength(String[] words) {
Arrays.sort(words, new Comparator<String>() {
public int compare (String s1, String s2) {
if (s1.length() < s2.length()) {
return -1;
}
else if (s1.length() > s2.length()) {
return 1;
}
else {
return 0;
}
}
});
}

// EFFECT: key is every char of the word, value is the frequency
//         ignore the case, change all the lowercase value to uppercase
public void enterWordToMap(String word, Map<Integer, Integer> map) {
for (char c : word.toCharArray()) {
int charVal = c - '0';
if (charVal >= 17 && charVal <= 42) {
map.put(charVal, map.getOrDefault(charVal, 0) + 1);
}
if (charVal >= 49 && charVal <= 74) {
int normCharVal = charVal - 32;
map.put(normCharVal, map.getOrDefault(normCharVal, 0) + 1);
}
}
}
}
``````

• HashMap here too, but shorter solution.

``````class Solution {
public String shortestCompletingWord(String licensePlate, String[] words) {
int minLen = Integer.MAX_VALUE;
String minLenWord = "";
HashMap<Character,Integer> map = new HashMap<>();
if(c >= 'a' && c <= 'z') {
increment(map,c,1);
}
}
for(String word : words) {
if(word.length() < minLen) {
HashMap<Character,Integer> charMap = (HashMap<Character,Integer>)map.clone();
for(char c : word.toCharArray()) {
increment(charMap,c,-1);
}
if(charMap.size() == 0) {
minLen = word.length();
minLenWord = word;
}
}
}
return minLenWord;
}

private void increment(HashMap<Character,Integer> map, char key, int delta) {
int newVal = map.getOrDefault(key,0) + delta;
if(newVal == 0) {
map.remove(key);
} else if(newVal > 0) {
map.put(key,newVal);
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.