Question

Formatted question description: https://leetcode.ca/all/1160.html

 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.


 Note:

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

Algorithm

We need to check whether the frequency of each character of each word meets the available frequency that the character can provide. In other words, if the character frequency of the current word is higher (for example, “hello” requires two “l”s and there is only one “l” in “helo”, then we need to skip the word). Calculate and sum the length of a word. If the cycle of each character of a word is completed, the length of the word.

Code

Java

public class Find_Words_That_Can_Be_Formed_by_Characters {


    public static void main(String[] args) {
        String[] words = {"cat","bt","hat","tree"};
        String chars = "atach";
        Find_Words_That_Can_Be_Formed_by_Characters find_words_that_can_be_formed_by_characters_1160 = new Find_Words_That_Can_Be_Formed_by_Characters();
        System.out.println(find_words_that_can_be_formed_by_characters_1160.new Solution().countCharacters(words, chars));
    }

    class Solution {
        public int countCharacters(String[] words, String chars) {
            if (chars.equals("") || words == null || words.length ==0){
                return 0;
            }
            HashMap<Character, Integer> map = new HashMap<>();

            for (int i = 0; i < chars.length(); i++) {
                if (map.get(chars.charAt(i)) == null){
                    map.put(chars.charAt(i), 1);
                } else {
                    map.put(chars.charAt(i), map.get(chars.charAt(i))+1);
                }
            }

            int ans = 0;
            HashMap<Character, Integer> temp = new HashMap<>(map);
            for (String word : words) {
                for (int i = 0; i < word.length(); i++) {
                    if (map.containsKey(word.charAt(i))){
                        map.put(word.charAt(i),map.get(word.charAt(i))-1);
                    }
                    if (map.get(word.charAt(i)) == null || map.get(word.charAt(i)) < 0){
                        break;
                    }
                    if (i == word.length()-1){
                        ans += word.length();
                    }
                }
                map = new HashMap<>(temp);
            }

            return ans;
        }
    }

}

Java

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

    public boolean canFormWord(String word, String chars) {
        int[] wordCount = new int[26];
        int[] charsCount = new int[26];
        char[] wordArray = word.toCharArray();
        for (char c : wordArray)
            wordCount[c - 'a']++;
        char[] charsArray = chars.toCharArray();
        for (char c : charsArray)
            charsCount[c - 'a']++;
        for (int i = 0; i < 26; i++) {
            if (wordCount[i] > charsCount[i])
                return false;
        }
        return true;
    }
}

All Problems

All Solutions