1160. Find Words That Can Be Formed by Characters LeetCode Solution
In this guide, you will get 1160. Find Words That Can Be Formed by Characters LeetCode Solution with the best time and space complexity. The solution to Find Words That Can Be Formed by Characters problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1160. Find Words That Can Be Formed by Characters LeetCode Solution in C++
class Solution {
public:
int countCharacters(vector<string>& words, string chars) {
int ans = 0;
vector<int> count(26);
for (const char c : chars)
++count[c - 'a'];
for (const string& word : words) {
vector<int> tempCount(count);
for (const char c : word)
if (--tempCount[c - 'a'] < 0) {
ans -= word.length();
break;
}
ans += word.length();
}
return ans;
}
}; /* code provided by PROGIEZ */
1160. Find Words That Can Be Formed by Characters LeetCode Solution in Java
class Solution {
public int countCharacters(String[] words, String chars) {
int ans = 0;
int[] count = new int[26];
for (final char c : chars.toCharArray())
++count[c - 'a'];
for (final String word : words) {
int[] tempCount = count.clone();
for (final char c : word.toCharArray())
if (--tempCount[c - 'a'] < 0) {
ans -= word.length();
break;
}
ans += word.length();
}
return ans;
}
} // code provided by PROGIEZ
1160. Find Words That Can Be Formed by Characters LeetCode Solution in Python
class Solution:
def countCharacters(self, words: list[str], chars: str) -> int:
ans = 0
count = collections.Counter(chars)
for word in words:
tempCount = count.copy()
for c in word:
tempCount[c] -= 1
if tempCount[c] < 0:
ans -= len(word)
break
ans += len(word)
return ans # code by PROGIEZ
