LeetCode学习笔记——单词拼写

个人博客：The Blog Of WaiterXiaoYY 欢迎来互相交流学习。

1160. 拼写单词

给你一份『词汇表』（字符串数组） 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.利用长度为26的数组，例如int []chars = new int[26]

2.记录单词表中每个word中各自字符出现的数量，同时也记录chars中字符的数量

3.对单词表words中的每个word进行遍历，当chars中的某字符数量小于word的字符数量时，则说明该单词不能被掌握，标记后跳过这个单词，遍历下一个。

需要注意的是，在进行统计一个字符串中每个字符的数量的时候，要将字符串转为数组的形式，

即String.toCharArray()，此时才可以对其进行挨个遍历。

代码

public int countCharacters(String[] words, String chars) {
    if(chars == null || words == null)
        return 0;
    int []cnt_chars = new int[26];   //用于统计chars中字符的数量
    int count = 0;  //单词长度计数
    int flag = 1;   //标记，用于判断该单词是否能被掌握
    //对chars进行遍历统计
    for(char c : chars.toCharArray())
        cnt_chars[c - 'a']++;
    //对单词表中每个word进行单独操作
    for(String word : words) {
        int []cnt_word = new int[26];   
        //统计每个单词字符的数量
        for(char c : word.toCharArray())
            cnt_word[c - 'a']++;
        //再次对该单词进行遍历，判断是否能被掌握
        for(char c : word.toCharArray()) {
            //如果chars中的字符数量小于word中，则标记不能被掌握，跳过这个单词
            if(cnt_chars[c - 'a'] < cnt_word[c - 'a']) {
                flag = 0;
                break;
            }
            flag = 1;  //需将标记更新
        }
        if(flag == 1)
            count += word.length();  //将单词长度加起来
    }
    return count;
}