README.md

1160. 拼写单词

English Version

题目描述

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。

假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。

注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。

返回词汇表 words 中你掌握的所有单词的 长度之和。

 

示例 1：

输入：words = ["cat","bt","hat","tree"], chars = "atach"
输出：6
解释： 
可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。

示例 2：

输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出：10
解释：
可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。

 

提示：

1. 1 <= words.length <= 1000
2. 1 <= words[i].length, chars.length <= 100
3. 所有字符串中都仅包含小写英文字母

解法

Python3

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        counter = Counter(chars)
        ans = 0
        for word in words:
            cnt = Counter(word)
            if all([counter[c] >= v for c, v in cnt.items()]):
                ans += len(word)
        return ans

Java

class Solution {
    public int countCharacters(String[] words, String chars) {
        int[] counter = count(chars);
        int ans = 0;
        for (String word : words) {
            int[] cnt = count(word);
            if (check(counter, cnt)) {
                ans += word.length();
            }
        }
        return ans;
    }

    private int[] count(String s) {
        int[] counter = new int[26];
        for (char c : s.toCharArray()) {
            ++counter[c - 'a'];
        }
        return counter;
    }

    private boolean check(int[] cnt1, int[] cnt2) {
        for (int i = 0; i < 26; ++i) {
            if (cnt1[i] < cnt2[i]) {
                return false;
            }
        }
        return true;
    }
}

C++

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        vector<int> counter = count(chars);
        int ans = 0;
        for (auto& word : words) {
            vector<int> cnt = count(word);
            if (check(counter, cnt)) ans += word.size();
        }
        return ans;
    }

    vector<int> count(string s) {
        vector<int> counter(26);
        for (char c : s) ++counter[c - 'a'];
        return counter;
    }

    bool check(vector<int>& cnt1, vector<int>& cnt2) {
        for (int i = 0; i < 26; ++i)
            if (cnt1[i] < cnt2[i]) return false;
        return true;
    }
};

Go

func countCharacters(words []string, chars string) int {
	counter := count(chars)
	ans := 0
	for _, word := range words {
		cnt := count(word)
		if check(counter, cnt) {
			ans += len(word)
		}
	}
	return ans
}

func count(s string) []int {
	counter := make([]int, 26)
	for _, c := range s {
		counter[c-'a']++
	}
	return counter
}

func check(cnt1, cnt2 []int) bool {
	for i := 0; i < 26; i++ {
		if cnt1[i] < cnt2[i] {
			return false
		}
	}
	return true
}

...