LeetCode 1160. 拼写单词

Categories:

题目描述
思路分析
1. 解法一：计数比对（推荐）
相似题目

题目描述

✅ 1160. 拼写单词

思路分析

解法一：计数比对（推荐）

核心思路：

统计字符池 chars 中每个字母的可用次数。

对每个单词统计频次，若任一字母超出可用次数则无法拼写。

累加所有可拼写单词的长度。

复杂度分析：

时间复杂度：O(total)，其中 total 表示所有单词字符总数。

空间复杂度：O(1)，固定 26 个字母计数。

class Solution {
    public int countCharacters(String[] words, String chars) {
        int[] base = new int[26];
        for (char c : chars.toCharArray()) {
            base[c - 'a']++;
        }

        int res = 0;
        for (String word : words) {
            int[] count = new int[26];
            boolean ok = true;
            for (char c : word.toCharArray()) {
                int idx = c - 'a';
                count[idx]++;
                if (count[idx] > base[idx]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                res += word.length();
            }
        }

        return res;
    }
}

func countCharacters(words []string, chars string) int {
	base := make([]int, 26)
	for i := 0; i < len(chars); i++ {
		base[chars[i]-'a']++
	}

	res := 0
	for _, word := range words {
		count := make([]int, 26)
		ok := true
		for i := 0; i < len(word); i++ {
			idx := word[i] - 'a'
			count[idx]++
			if count[idx] > base[idx] {
				ok = false
				break
			}
		}
		if ok {
			res += len(word)
		}
	}

	return res
}

相似题目

题目	难度	考察点
383. 赎金信	简单	计数
242. 有效的字母异位词	简单	计数
438. 找到字符串中所有字母异位词	中等	计数
1002. 查找共用字符	简单	计数
1189. “气球” 的最大数量	简单	计数

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/31165303