1160. 拼写单词

Posted on | In
Words count in article: 390 | Reading time ≈ 1

题目

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。

假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。

注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。

返回词汇表 words 中你掌握的所有单词的 长度之和。

示例1：

1
2
3
4
5
输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释： 
可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。

示例2：

1
2
3
4
输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出：10
解释：
可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。

提示：

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

解法

解法一：

借助HashMap。

Java

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
29
30
31
32
public int countCharacters(String[] words, String chars) {
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		for (char c : chars.toCharArray()) {
			if (map.containsKey(c)) {
				map.replace(c, map.get(c) + 1);
			} else {
				map.put(c, 1);
			}
		}
		
		int sum = 0;
		for (String word : words) {
			if (containsWord(word, map)) {
				sum += word.length();
			}
		}
		return sum;
    }
	
	private boolean containsWord(String word, Map<Character, Integer>map ) {
		Map<Character, Integer> wordMap = new HashMap<>();
		for (char c : word.toCharArray()) {
			wordMap.put(c, wordMap.getOrDefault(c, 0) + 1);
		}
		
		for (char key : wordMap.keySet()) {
			if (!map.containsKey(key) || wordMap.get(key) > map.get(key)) {
				return false;
			}
		}
		return true;
	}
0%