Easy

题目描述

给你一个单词数组 words 和一个字符串 chars。

如果一个单词可以由 chars 中的字符组成，则称这个单词是 好 的（字符串 chars 中的每个字符都只能用一次）。

返回 words 中所有好单词的 长度之和。

示例 1：

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

示例 2：

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

提示：

  • 1 <= words.length <= 1000
  • 1 <= words[i].length, chars.length <= 100
  • words[i] 和 chars 仅包含小写英文字母

解题思路

这道题的核心思想是字符频次统计。我们需要判断每个单词是否可以由给定的字符集合构成。

解题思路：

  1. 统计字符频次：首先统计 chars 中每个字符的出现次数，这相当于我们的"字符库存"。

  2. 逐个检查单词：对于 words 中的每个单词，统计其字符频次，然后检查是否每个字符的需求量都不超过字符库存中的数量。

  3. 累计长度：如果一个单词可以被构成（即所有字符的需求都能被满足），就将其长度加入结果。

具体实现：

  • 使用哈希表或数组（因为只有26个小写字母）来统计字符频次
  • 为了避免修改原始的字符频次表，可以为每个单词创建临时的频次表进行比较
  • 另一种方法是直接模拟"使用"字符的过程，检查完一个单词后恢复字符数量

时间复杂度优化： 由于只涉及小写英文字母，使用固定大小的数组比哈希表更高效。

代码实现

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        // 统计chars中每个字符的频次
        vector<int> charCount(26, 0);
        for (char c : chars) {
            charCount[c - 'a']++;
        }
        
        int result = 0;
        for (const string& word : words) {
            // 统计当前单词中每个字符的频次
            vector<int> wordCount(26, 0);
            for (char c : word) {
                wordCount[c - 'a']++;
            }
            
            // 检查是否可以构成当前单词
            bool canForm = true;
            for (int i = 0; i < 26; i++) {
                if (wordCount[i] > charCount[i]) {
                    canForm = false;
                    break;
                }
            }
            
            if (canForm) {
                result += word.length();
            }
        }
        
        return result;
    }
};

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        from collections import Counter
        
        # 统计chars中每个字符的频次
        char_count = Counter(chars)
        result = 0
        
        for word in words:
            # 统计当前单词中每个字符的频次
            word_count = Counter(word)
            
            # 检查是否可以构成当前单词
            can_form = True
            for char, count in word_count.items():
                if count > char_count.get(char, 0):
                    can_form = False
                    break
            
            if can_form:
                result += len(word)
        
        return result

public class Solution {
    public int CountCharacters(string[] words, string chars) {
        // 统计chars中每个字符的频次
        int[] charCount = new int[26];
        foreach (char c in chars) {
            charCount[c - 'a']++;
        }
        
        int result = 0;
        foreach (string word in words) {
            // 统计当前单词中每个字符的频次
            int[] wordCount = new int[26];
            foreach (char c in word) {
                wordCount[c - 'a']++;
            }
            
            // 检查是否可以构成当前单词
            bool canForm = true;
            for (int i = 0; i < 26; i++) {
                if (wordCount[i] > charCount[i]) {
                    canForm = false;
                    break;
                }
            }
            
            if (canForm) {
                result += word.Length;
            }
        }
        
        return result;
    }
}

var countCharacters = function(words, chars) {
    // 统计chars中每个字符的频次
    const charCount = new Array(26).fill(0);
    for (const c of chars) {
        charCount[c.charCodeAt(0) - 97]++;
    }
    
    let result = 0;
    for (const word of words) {
        // 统计当前单词中每个字符的频次
        const wordCount = new Array(26).fill(0);
        for (const c of word) {
            wordCount[c.charCodeAt(0) - 97]++;
        }
        
        // 检查是否可以构成当前单词
        let canForm = true;
        for (let i = 0; i < 26; i++) {
            if (wordCount[i] > charCount[i]) {
                canForm = false;
                break;
            }
        }
        
        if (canForm) {
            result += word.length;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(N + M)N为chars长度，M为所有words中字符总数
空间复杂度O(1)使用固定大小的数组存储字符频次（26个字母）

相关题目