LeetCode.1160.Find Words That Can Be Formed by Characters 拼写单词

题目描述

1160 Find Words That Can Be Formed by Characters
https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters/

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

Example 1:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation:
The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2:

Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation:
The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

Note:
1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
All strings contain lowercase English letters only.

---

解题过程

时间复杂度 O(nml)，其中 单词个数n，平均单词长度 m，字典长度 l
空间复杂度 O(l) l是字典长度

优化：其实并不需要每次都初始化一个存放字母表的map，只初始化一次即可，然后每个单词也做成map形式，比较字母表的字母个数总能覆盖（大于等于）单词的字母个数即可。

private static class SolutionV2020 {
    public int countCharacters(String[] words, String chars) {
        if (null == words || 0 == words.length || null == chars || chars.length() == 0) {
            return 0;
        }
        int sum = 0;

        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            boolean good = true;
            // 每次都要初始化字典表
            Map<String, Integer> dictMap = initDictMap(chars);
            for (int j = 0; j < word.length(); j++) {
                String ch = String.valueOf(word.charAt(j));
                if (dictMap.getOrDefault(ch, 0) == 0) {
                    good = false;
                    break;
                } else {
                    dictMap.put(ch, dictMap.get(ch) - 1);
                }
            }
            if (good) {
                sum += word.length();
            }
        }
        return sum;
    }

    // 初始化字典 map， 字符 -> 出现次数
    private Map<String, Integer> initDictMap(String chars) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < chars.length(); i++) {
            String ch = String.valueOf(chars.charAt(i));
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        return map;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_1160_FindWordsThatCanBeFormedByCharacters.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_1160_FindWordsThatCanBeFormedByCharacters.java

---