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

推荐阅读:
黑木耳营养丰富对健康有五大好处  香蕉和橘子能起到解毒护肝的作用  吃葡萄、喝葡萄酒能帮助调节性功能  绿茶、红茶、青茶、黑茶、白茶和黄茶  奶茶多添加奶精 长期食用会引发心脏病  奶茶调查:街头奶茶店调香味多用奶精  适合秋天食用的养肺食谱可滋阴润肺  哪些食物可以起到止咳润肺的作用  食物的禁忌:中医如何区分食物的寒热性  味道鲜美营养丰富的黑木耳最佳吃法 
评论列表
添加评论