leetcode
leetcode 951 ~ 1000
拼写单词

拼写单词

难度:

标签:

题目描述

代码结果

运行时间: 42 ms, 内存: 16.3 MB


/**
 * This solution uses Java Streams to count the total length of words that can be formed.
 * We use a frequency map to count the characters in chars and then filter the words that can be formed.
 * The lengths of the filtered words are summed up to get the total length.
 */

import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Solution {
    public int countCharacters(String[] words, String chars) {
        int[] charCount = new int[26];
        chars.chars().forEach(c -> charCount[c - 'a']++);
        return Stream.of(words)
                .filter(word -> canFormWord(word, charCount.clone()))
                .mapToInt(String::length)
                .sum();
    }

    private boolean canFormWord(String word, int[] charCount) {
        return word.chars().allMatch(c -> --charCount[c - 'a'] >= 0);
    }
}

解释

方法:

此题解通过检查每个单词的每个字符是否可以由字符表`chars`中的字符组成来决定是否可以拼写该单词。对于每个单词,遍历其所有字符,使用字符串的`count`方法检查该字符在单词中出现的次数是否不超过该字符在字符表中的次数。如果所有字符都满足条件,则将该单词的长度累加到总长度中。

时间复杂度:

O(L*(m+n))

空间复杂度:

O(1)

代码细节讲解

🦆
为什么选择使用字符串的`count`方法来检查字符数量,而不是构建字符的哈希表来优化查找和比较的效率?
使用字符串的`count`方法是一种直观的方法来检查字符数量,尤其是在简单或较小的输入上效率尚可接受。然而,这种方法的时间复杂度较高,因为每次调用`count`都需要遍历整个字符串来统计字符。构建字符的哈希表(例如字典)可以显著优化查找和比较的效率,尤其是在处理大量数据或需要频繁查询的情况下。通过先统计每个字符的出现次数存入哈希表,之后的查找操作可以在常数时间内完成,从而减少整体的时间复杂度。
🦆
题解中提到如果单词中某字符的数量超过`chars`中的数量则不再检查其他字符,这种策略是否总是最优的?是否有可能通过其他方式减少不必要的字符比较?
题解中提到的策略是有效的,因为一旦发现有一个字符不满足条件,整个单词就无法由`chars`拼写。这种提前终止检查的策略是优化性能的一种常见方式,可以避免对已确定无法拼写的单词进行更多无用的字符检查。然而,使用哈希表存储字符出现频率而非多次调用`count`方法也是减少不必要比较的一种方式,可以进一步提高效率。
🦆
题解中没有提到对输入的验证,如何处理`chars`为空或`words`为空的情况?这会影响算法的执行和结果吗?
如果`chars`为空,则无论`words`中的单词如何,都无法拼写任何单词,因为没有字符可用。如果`words`为空,则没有单词需要检查,因此返回的总长度应为0。处理这些边界情况是重要的,可以通过在函数开始添加简单的检查来实现。例如,如果`chars`为空或`words`为空,则直接返回0。这不仅可以避免不必要的计算,还可以防止潜在的运行时错误。

相关问题