# LWC 63：748. Shortest Completing Word

## LWC 63：748. Shortest Completing Word

Problem:

Find the minimum length word from a given dictionary words, which has all the letters from the string licensePlate. Such a word is said to complete the given string licensePlate Here, for letters we ignore case. For example, “P” on the licensePlate still matches “p” on the word. It is guaranteed an answer exists. If there are multiple answers, return the one that occurs first in the array. The license plate might have the same letter occurring multiple times. For example, given a licensePlate of “PP”, the word “pair” does not complete the licensePlate, but the word “supper” does.

Example 1:

Input: licensePlate = “1s3 PSt”, words = [“step”, “steps”, “stripe”, “stepple”] Output: “steps” Explanation: The smallest length word that contains the letters “S”, “P”, “S”, and “T”. Note that the answer is not “step”, because the letter “s” must occur in the word twice. Also note that we ignored case for the purposes of comparing whether a letter exists in the word.

Example 2:

Input: licensePlate = “1s3 456”, words = [“looks”, “pest”, “stew”, “show”] Output: “pest” Explanation: There are 3 smallest length words that contains the letters “s”. We return the one that occurred first.

Note:

licensePlate will be a string with length in range [1, 7].

licensePlate will contain digits, spaces, or letters (uppercase or lowercase).

words will have a length in the range [10, 1000].

Every words[i] will consist of lowercase letters, and have length in range [1, 15].

Java版本：

    public String shortestCompletingWord(String licensePlate, String[] words) {
String ans = "";
int minLen = 1111;

int[] map = new int[32];
if (c >= 'a' && c <= 'z') map[c - 'a'] ++;

for (String word : words) {
int len = word.length();
if (contains(map, word)) {
if (len < minLen) {
ans = word;
minLen = len;
}
}
}
return ans;
}

boolean contains(int[] map, String word) {
int[] map2 = new int[32];
for (char c : word.toLowerCase().toCharArray()) {
map2[c - 'a'] ++;
}

for (int i = 0; i < 32; ++i) {
if (map[i] != 0) {
if (map2[i] < map[i]) return false;
}
}
return true;
}

Python版本：

    def shortestCompletingWord(self, licensePlate, words):
"""
:type words: List[str]
:rtype: str
"""
d = dict()
for c in licence_plate:
if c.isalpha():
if c not in d:
d[c] = 0
d[c] += 1

res = None
length = 1111
for word in words:
freq = d.copy()
for c in word:
if c in freq:
freq[c] -= 1
if freq[c] == 0:
freq.pop(c)
if not freq:
if len(word) < length:
res = word
length = len(word)

return res 

0 条评论

## 相关文章

1114

4105

1340

### 程序员必知的8大排序（java实现）

8种排序之间的关系: ? 　1、 直接插入排序 　　（1）基本思想： 　　在要排序的一组数中，假设前面(n-1)[n>=2] 个数已经是排好顺序的，现在要...

19910

### Java 关于集合框架那点事儿

1.引入集合框架   采用数组存在的一些缺陷：    1.数组长度固定不变，不能很好地适应元素数量动态变化的情况。    2.可通过数组名.length获取数...

28710

2023

783

1956

4587

1121