LeeCode刷题记录4------拼写单词(简单)

题目描述:

给你一份词汇表(字符串数组)words 和一张字母表(字符串)chars
假如你可以用 chars中的字母(字符)拼写出 words 中的某个单词(字符串),那么我们就认为你掌握了这个单词。

注意:

每次拼写(指拼写词汇表中的一个单词)时,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
所有字符串中都仅包含小写英文字母

思路分析:

因为所有字符串仅包含小写的英文字母,那么我们就可以构建一个长度为26的字符数组,来分别表示每个字母的出现次数,以便进行对比和计算。
在此题中:

  1. cLetter数组来存储字母表中每个字母出现的次数。
  2. 对于每个单词都创建一个wLetter数组来存储该单词所需的每个字母的个数。
  3. 比较cLetter数组和wLetter数组的对应位置。
  4. 如果wLetter数组中的数都不大于cLetter数组中对应位置的数,那么说明改单词能够被拼写出来,则将该单词的长度计入返回结果中。
    5.如果如果wLetter数组中的数有一个大于了cLetter数组中对应位置的数,则说明该单词不能被拼写出来,则无需进行其他字母的比较,直接跳转到下一个单词进行比较。

代码实现:

class Solution {
    public int countCharacters(String[] words, String chars) {
        int res = 0;
        int[] cLetter = new int[26];
        for (char c : chars.toCharArray()) {
            cLetter[(int)(c - 'a')] += 1;
        }
        loop: for (int i = 0; i < words.length ; i++) {
            int[] wLetter = new int[26];
            for (char w : words[i].toCharArray()) {
                wLetter[(int)(w - 'a')] += 1;
            }
            for (int j = 0; j < 26 ; j++) {
                if (wLetter[j] > cLetter[j] ){
                    //只要判断出所需字母数大于已有字母数,结束当前的循环,跳转至下一个单词的对比判断
                    continue loop;
                }
            }
            res = res + words[i].toCharArray().length;
        }
        return res;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。