[LeetCode] 1160. 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.

Constraints:
1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
words[i] and chars consist of lowercase English letters.

拼写单词。

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。
注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。
返回词汇表 words 中你掌握的所有单词的 长度之和。

思路

用一个长度为26的 int array 统计字母表中每个不同字母的出现次数，然后遍历词汇表中的每个单词，看看字母表中的字母是否足够组成当前的单词，如果能组成，则将当前单词的长度累加到结果。

复杂度

时间O(mn) - m 个单词，单词平均长度为 n
空间O(m) - 要将长度为26的 int array复制 m 次

代码

Java实现

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

        int count = 0;
        for (String word : words) {
            int[] letters = map.clone();
            if (helper(word, letters)) {
                count += word.length();
            }
        }
        return count;
    }

    private boolean helper(String word, int[] letters) {
        for (char c : word.toCharArray()) {
            if (letters[c - 'a'] > 0) {
                letters[c - 'a']--;
            } else {
                return false;
            }
        }
        // System.out.println(word);
        return true;
    }
}