Algorithm
Problem Name: 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 <= 10001 <= words[i].length, chars.length <= 100words[i]andcharsconsist of lowercase English letters.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int countCharacters(String[] words, String chars) {
Map frequency = getFrequencyMap(chars);
return Arrays.stream(words)
.filter(word -> canBeFormed(word, frequency))
.map(word -> word.length())
.reduce(0, Integer::sum);
}
private boolean canBeFormed(String word, Map < Character, Integer> frequency) {
Map wordFrequency = getFrequencyMap(word);
for (Character key : wordFrequency.keySet()) {
if (frequency.getOrDefault(key, 0) < wordFrequency.get(key)) {
return false;
}
}
return true;
}
private Map < Character, Integer> getFrequencyMap(String s) {
Map frequency = new HashMap<>();
for (char c : s.toCharArray()) {
frequency.put(c, frequency.getOrDefault(c, 0) + 1);
}
return frequency;
}
}
Input
words = ["cat","bt","hat","tree"], chars = "atach"
Output
6
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const countCharacters = function(words, chars) {
let letters = new Array(26).fill(0),
a = 'a'.charCodeAt(0),
z = 'z'.charCodeAt(0)
let count = 0
for (let i = 0; i < chars.length; i++) {
let l = chars[i].charCodeAt(0) - a
letters[l]++
}
for (let i = 0; i < words.length; i++) {
let word = words[i]
let tmp = letters.slice()
let tCount = 0
for (let j = 0; j < word.length; j++) {
let l = word[j].charCodeAt(0) - a
tmp[l]--
if (tmp[l] < 0) {
break
} else {
tCount++
}
}
if (tCount == word.length) {
count += word.length
}
}
return count
}
Input
words = ["cat","bt","hat","tree"], chars = "atach"
Output
6
#3 Code Example with Python Programming
Code -
Python Programming
from collections import Counter as cnt
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
return sum(not cnt(w) - cnt(chars) and len(w) for w in words)
Input
words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output
10
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _1160_FindWordsThatCanBeFormedByCharacters
{
public int CountCharacters(string[] words, string chars)
{
if (string.IsNullOrWhiteSpace(chars)) return 0;
var charMap = new int[26];
foreach (var ch in chars)
charMap[ch - 'a']++;
var result = 0;
var temp = new int[26];
foreach (var word in words)
{
charMap.CopyTo(temp, 0);
var isGood = true;
foreach (var ch in word)
{
if (temp[ch - 'a'] > 0)
temp[ch - 'a']--;
else
{
isGood = false;
break;
}
}
if (isGood) result += word.Length;
}
return result;
}
}
}
Input
words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output
10