1160. Find Words That Can Be Formed by Characters

1160. Find Words That Can Be Formed by Characters #

题目 #

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

Example 1:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: 
The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2:

Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: 
The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

Note:

  1. 1 <= words.length <= 1000
  2. 1 <= words[i].length, chars.length <= 100
  3. All strings contain lowercase English letters only.

题目大意 #

给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars。假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字符串),那么我们就认为你掌握了这个单词。注意:每次拼写时,chars 中的每个字母都只能用一次。返回词汇表 words 中你掌握的所有单词的 长度之和。

提示:

  1. 1 <= words.length <= 1000
  2. 1 <= words[i].length, chars.length <= 100
  3. 所有字符串中都仅包含小写英文字母

解题思路 #

  • 给出一个字符串数组 words 和一个字符串 chars,要求输出 chars 中能构成 words 字符串的字符数总数。
  • 简单题。先分别统计 wordschars 里面字符的频次。然后针对 words 中每个 word 判断能够能由 chars 构成,如果能构成,最终结果加上这个 word 的长度。

代码 #


package leetcode

func countCharacters(words []string, chars string) int {
	count, res := make([]int, 26), 0
	for i := 0; i < len(chars); i++ {
		count[chars[i]-'a']++
	}
	for _, w := range words {
		if canBeFormed(w, count) {
			res += len(w)
		}
	}
	return res
}
func canBeFormed(w string, c []int) bool {
	count := make([]int, 26)
	for i := 0; i < len(w); i++ {
		count[w[i]-'a']++
		if count[w[i]-'a'] > c[w[i]-'a'] {
			return false
		}
	}
	return true
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者