yokolet's notelets

  1. Strings
  2. Find Words That Can Be Formed by Characters

Strings

Find Words That Can Be Formed by Characters

Problem Description

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.

Constraints:

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

Examples

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.

How to Solve

This is a kind of anagram problem. A hash table is a good data structure to solve this problem. Two types of hash tables are necessary: one for the given chars, another for each word. If we compare these two hash tables, it’s not difficult to find the answer.

The first step is to create a character frequency table for chars. To check each word in the word list, create another frequency table for the word. The condition to add up the word length is:

  • all characters in the word frequency table exist in the given chars’ frequency table
  • the given chars’ character count is greater than or equal to the word’s character

If two conditions meet, the word length is added to the result.

Solution

  • 
    
  • 
    
  • 
    
  • class FindWordsThatCanBeFormedByCharacters:
        def countCharacters(self, words: List[str], chars: str) -> int:
            counter = collections.Counter(chars)
    
            def isGood(word):
                w_cnt = collections.Counter(word)
                for k, v in w_cnt.items():
                    if k not in counter or counter[k] < v:
                        return False
                return True
            
            result = 0
            for word in words:
                if isGood(word):
                    result += len(word)
            return result
    
  • # @param {String[]} words
    # @param {String} chars
    # @return {Integer}
    def count_characters(words, chars)
        freq = chars.chars.tally
        words.map {|word| good_length(freq, word)}.sum
    end
    
    def good_length(freq, word)
      cur_freq = word.chars.tally
      cur_freq.each_pair do |char, count|
        if !freq.has_key?(char) || freq[char] < count
          return 0
        end
      end
       word.length
    end
    

Complexities

  • Time: O(m + n) – m: length of chars, n: number of words
  • Space: O(m + k) – k : length of each word
Easy
Hash Table
String