力扣每日一题之最短补全词

发表于

给你一个字符串licensePlate和一个字符串数组words，请你找出并返回words中最短补全词。

补全词是一个包含licensePlate中所有字母的单词，在所有补全词中，最短的那个就是最短补全词。

  • 在匹配licensePlate中的数字或空格。
  • 不区分大小写
  • 如果某个字母在licensePlace中出现不止一次，那么该字母在补全词中的出现的次数也应当一致或者更多。

例如：licensePlate=aBc 12c, 那么他的补全词应当包含字母a、b忽略大小写和两个c，可能的补全词有abccdef、caaacab以及cbca。

请你找出并返回words中的最短补全词。题目数据中保证一定存在一个最短补全词。当有多个单词都符合最短补全词的匹配条件时区words中最靠前的那个。

方法一：统计字符出现次数

根据题意，先统计licesePlate中每个字母的出现次数（忽略大小写），然后遍历words中的每个单词，若26个英文字母在该单词中初选次数均小于licesePlate中才出现的次数，则该单词是一个补全词。返回最短且最靠前的补全词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package main

import "unicode"

func shortestCompletingWord(licensePlate string, words []string) (ans string) {
	cnt := [26]int{}
	for _, ch := range licensePlate {
		if unicode.IsLetter(ch) { // 如果是字母
			cnt[unicode.ToLower(ch)-'a'] += 1 // 就让他变成小写
		}
	}
next:
	for _, word := range words {
		c := [26]int{}
		for _, ch := range word {
			c[ch-'a'] += 1
		}
		for i := 0; i < 26; i++ {
			if c[i] < cnt[i] {
				continue next
			}
		}
		if ans == "" || len(word) < len(ans) {
			ans = word
		}
	}
	return
}