【leetcode】1160. 拼写单词（find-words-that-can-be-formed-by-characters）（字符串）[简单]

链接

https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters/

耗时

解题：10 min+
题解：35 min

题意

现有一个字符串数组 words 和一个字符串 chars，求 words 中所有可以用 chars 中的字母拼出 words 中的单词的长度之和，并且每次拼写时，chars 中的每个字母都只能用一次。（所有字符串中都仅包含小写英文字母）

思路

首先记录下 chars 中每个字母的个数，然后与 words 中的一个单词的每个字母的个数对比，若这个单词中出现的每个字母的个数都小于等于 chars 中相对应的字母的个数，那么显然可以用 chars 中的字母拼出这个单词，否则肯定不能。如此比较 words 中的每一个单词，累加 可以拼出的单词的长度 即可。时间复杂度最多 O( 1 0 5 10^5 105)。

AC代码

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        int lech[30] = {0};
        for(int i = 0; i < chars.size(); ++i) {
            lech[chars[i]-'a']++;
        }
        int ans = 0;
        for(int i = 0; i < words.size(); ++i) {
            int lewo[30] = {0};
            for(int j = 0; j < words[i].size(); ++j) {
                lewo[words[i][j]-'a']++;
            }
            bool flag = true;
            for(int j = 0; j < 26; ++j) {
                if(lewo[j] > lech[j]) {
                    flag = false;
                    break;
                }
            }
            if(flag) ans += words[i].size();
        }
        return ans;
    }
};