给定一个字符串数组 words 和一个字符串 chars 如果一个字符串能被 chars 里面的字符组成那么这个字符串就是好的chars里面每个字符只能使用一次。求:words 里面所有好的字符串的字符总个数。比如:words = cat bt hat treechars = atach好的字符串有 cat hat 3 + 3 = 6输出:6Java
首先,我们可以使用一个HashMap来记录chars中每个字符出现的次数。
然后,我们遍历words数组,对于每个单词,我们都新建一个HashMap来记录单词中每个字符出现的次数。
接下来,我们遍历单词中的每个字符,如果该字符在chars的HashMap中出现的次数小于等于单词中对应字符出现的次数,说明该字符可以用来构成该单词,我们就将该字符出现的次数加到结果中。
最后,返回结果即可。
以下是Java代码实现:
import java.util.HashMap;
public class Solution {
public int countCharacters(String[] words, String chars) {
int count = 0;
HashMap<Character, Integer> charsMap = new HashMap<>();
for (char c : chars.toCharArray()) {
charsMap.put(c, charsMap.getOrDefault(c, 0) + 1);
}
for (String word : words) {
HashMap<Character, Integer> wordMap = new HashMap<>();
boolean isGood = true;
for (char c : word.toCharArray()) {
wordMap.put(c, wordMap.getOrDefault(c, 0) + 1);
if (!charsMap.containsKey(c) || charsMap.get(c) < wordMap.get(c)) {
isGood = false;
break;
}
}
if (isGood) {
count += word.length();
}
}
return count;
}
}
时间复杂度分析:假设words数组长度为n,chars字符串长度为m。遍历chars字符串构建HashMap的时间复杂度为O(m),遍历words数组时间复杂度为O(n),遍历单词中的每个字符的时间复杂度为O(k),其中k为单词的平均长度。因此,总的时间复杂度为O(n * k * m)。
空间复杂度分析:使用了两个HashMap来记录字符出现的次数,因此空间复杂度为O(m + k)
原文地址: https://www.cveoy.top/t/topic/ipFH 著作权归作者所有。请勿转载和采集!