How to Find Words That Can Be Formed by Characters?

  • 时间:2020-09-20 14:08:18
  • 分类:网络文摘
  • 阅读:97 次

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) —

推荐阅读:
How to Find the Dominant Index in Array (Largest Number At Least  K Closest Points to Origin Algorithm by using Priority Queues in  Total Number of Ways to Decode the Message via Dynamic Programmi  The License Key Formatting Algorithm in C++  Integrating LinkedIn Long-Form Posts in Your Blogging Strategy  A Quick Guide on Beefing Up Your WordPress Security  10 Proven Ways to Destroy Writer’s Block  3 Chrome Blogging Extensions to Watch Out for 2015  Cloud-Based Tools to Stake Your Business Blog On  How To Protect Your Brand On Social Media 
评论列表
添加评论