How to Find Words That Can Be Formed by Characters?
- 时间:2020-09-20 14:08:18
- 分类:网络文摘
- 阅读:112 次
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) —
推荐阅读:SEO收录异常诊断:负载均衡架构导致的SEO问题及解决方案 宝塔面板出现漏洞,站长如何做才能让网站更加安全? 掌握这7大SEO优化技巧,提高网站自然排名 网络推广SEO优化是怎么做的? 工信部ICP备案备案系统全新改版,速度更快,用户体验更好 影响网站排名的反向链接细节因素盘点 seo优化六步走网站优化基础策略分享 SEO赚不到钱是病,得治! 影响网站排名的反向链接细节因素盘点 百度上线API主动推送功能
- 评论列表
-
- 添加评论