How to Find Words That Can Be Formed by Characters?
- 时间:2020-09-20 14:08:18
- 分类:网络文摘
- 阅读:114 次
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.Hints:
- Solve the problem for each string in words independently.
- Now try to think in frequency of letters.
- Count how many times each character occurs in string chars.
- To form a string using characters from chars, the frequency of each character in chars must be greater than or equal the frequency of that character in the string to be formed.
Count the Frequency
We can count the frequencies for each letters (they are lower-case letters), and we can store them in a static int[26] array or hash map if the given characters are of broad ranges.
Then, we can go through the list of words, and check one by one if it can be formed by using the characters – reduce the frequency of a character and return false if it falls below zero.
The space complexity is constant O(1) as we only allocate a counter array with fixed size 26. The time complexity is O(Max(N, MO)) where N is the size of the input character set i.e. chars, and the M is the number of words in the list, and the O is the average size of the words in the list.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | class Solution { public: int countCharacters(vector<string>& words, string chars) { int ans = 0; int count[26]; std::fill(begin(count), end(count), 0); for (const auto &n: chars) { count[n - 97] ++; } for (const auto &s: words) { int cc[26]; std::copy(begin(count), end(count), begin(cc)); if (canWordBeFormedBy(s, cc)) { ans += s.size(); } } return ans; } private: bool canWordBeFormedBy(const string &s, int count[26]) { for (const auto &n: s) { if (count[n - 97] == 0) { return false; } count[n - 97] --; } return true; } }; |
class Solution { public: int countCharacters(vector<string>& words, string chars) { int ans = 0; int count[26]; std::fill(begin(count), end(count), 0); for (const auto &n: chars) { count[n - 97] ++; } for (const auto &s: words) { int cc[26]; std::copy(begin(count), end(count), begin(cc)); if (canWordBeFormedBy(s, cc)) { ans += s.size(); } } return ans; } private: bool canWordBeFormedBy(const string &s, int count[26]) { for (const auto &n: s) { if (count[n - 97] == 0) { return false; } count[n - 97] --; } return true; } };
Here, we use the std::fill to initialise the counter array to all zeros. And std::copy to copy an array to another in C++.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:都是马虎惹的祸作文700字 写人作文我们的周老师作文400字 雨水和想念 医生手上的苍蝇作文600字 What You Need if You Want to Be a Freelancer Best Ways to Maximize the Speed & Performance of Your Word Essential Google Chrome Extensions For SEO 10 Inspiring Home Improvement Blogs How to Get More Comments For Your Blog Posts Gmail Hacks and Tips for Bloggers
- 评论列表
-
- 添加评论