1160、拼写单词

leetcode

Created At : 2020-07-26 00:19

Count:478 Views 👀 :

Comment:

示例 1：
示例 2：

题解

1、统计每个单词中的字符的个数
2、在统计单词中字符的个数的时候进行比较

给你一份『词汇表』（字符串数组） 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
所有字符串中都仅包含小写英文字母

链接：https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters

题解

1、统计每个单词中的字符的个数

class Solution {
    public int countCharacters(String[] words, String chars) {
        int [] chs = statisticChar(chars);
        int length = 0;
        for (String word : words) {
            int [] wordChs = statisticChar(word);
            boolean canSpell = true;
            for (int i = 0;i < wordChs.length;i++) {
                if (chs[i] < wordChs[i]){
                    canSpell = false;
                    break;
                }
            }
            if (canSpell) {
                length += word.length();
            }
        }
        return length;
    }

    private int[] statisticChar(String chars) {
        int[] chs = new int[26];
        for (char ch : chars.toCharArray()) {
            chs[ch - 'a']++;
        }
        return chs;
    }
}

2、在统计单词中字符的个数的时候进行比较

class Solution {
    public int countCharacters(String[] words, String chars) {
        int [] chs = statisticChar(chars);
        int length = 0;
        for (String word : words) {
            if (canSpell(word,chs)) {
                length += word.length();
            }
        }
        return length;
    }

    private int[] statisticChar(String chars) {
        int[] chs = new int[26];
        for (char ch : chars.toCharArray()) {
            chs[ch - 'a']++;
        }
        return chs;
    }

    private boolean canSpell(String word,int[] chs) {
        int[] wordChs = new int[26];
        for (char ch : word.toCharArray()) {
            if (wordChs[ch - 'a'] == chs[ch - 'a']) {
                return false;
            }
            wordChs[ch - 'a']++;
        }
        return true;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com