1160. Find Words That Can Be Formed by Characters

leetcode easy

#array#csharp#easy#hash-table#leetcode#search#string#tree

Task

Вам дан массив строк words и строка chars.

Строка считается хорошей, если она может быть составлена из символов chars (каждый символ может быть использован только один раз).

Верните сумму длин всех хороших строк в words.

Пример:

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.

C# solution

matched/original

public class Solution {
    public int CountCharacters(string[] words, string chars) {
        var counts = new Dictionary<char, int>();
        foreach (var c in chars) {
            if (!counts.ContainsKey(c)) {
                counts[c] = 0;
            }
            counts[c]++;
        }
        
        int ans = 0;
        foreach (var word in words) {
            var wordCount = new Dictionary<char, int>();
            foreach (var c in word) {
                if (!wordCount.ContainsKey(c)) {
                    wordCount[c] = 0;
                }
                wordCount[c]++;
            }
            
            bool good = true;
            foreach (var kv in wordCount) {
                if (counts.GetValueOrDefault(kv.Key, 0) < kv.Value) {
                    good = false;
                    break;
                }
            }
            
            if (good) {
                ans += word.Length;
            }
        }
        
        return ans;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int CountCharacters(vector<string> words, string chars) {
        var counts = new unordered_map<char, int>();
        foreach (var c in chars) {
            if (!counts.count(c)) {
                counts[c] = 0;
            }
            counts[c]++;
        }
        
        int ans = 0;
        foreach (var word in words) {
            var wordCount = new unordered_map<char, int>();
            foreach (var c in word) {
                if (!wordCount.count(c)) {
                    wordCount[c] = 0;
                }
                wordCount[c]++;
            }
            
            bool good = true;
            foreach (var kv in wordCount) {
                if (counts.GetValueOrDefault(kv.Key, 0) < kv.Value) {
                    good = false;
                    break;
                }
            }
            
            if (good) {
                ans += word.size();
            }
        }
        
        return ans;
    }
}

Java solution

matched/original

class Solution {
    public int countCharacters(String[] words, String chars) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : chars.toCharArray()) {
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }
        
        int ans = 0;
        for (String word : words) {
            Map<Character, Integer> wordCount = new HashMap<>();
            for (char c : word.toCharArray()) {
                wordCount.put(c, wordCount.getOrDefault(c, 0) + 1);
            }
            
            boolean good = true;
            for (Map.Entry<Character, Integer> entry : wordCount.entrySet()) {
                if (counts.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
                    good = false;
                    break;
                }
            }
            
            if (good) {
                ans += word.length();
            }
        }
        
        return ans;
    }
}

JavaScript solution

matched/original

var countCharacters = function(words, chars) {
    const counts = {};
    for (let c of chars) {
        counts[c] = (counts[c] || 0) + 1;
    }
    
    let ans = 0;
    for (let word of words) {
        const wordCount = {};
        for (let c of word) {
            wordCount[c] = (wordCount[c] || 0) + 1;
        }
        
        let good = true;
        for (let c in wordCount) {
            if (counts[c] < wordCount[c]) {
                good = false;
                break;
            }
        }
        
        if (good) {
            ans += word.length;
        }
    }
    
    return ans;
};

Python solution

matched/original

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        counts = collections.Counter(chars)
        ans = 0
        
        for word in words:
            wordCount = collections.Counter(word)
            good = True
            for c, freq in wordCount.items():
                if counts[c] < freq:
                    good = False
                    break
            
            if good:
                ans += len(word)
        
        return ans

Explanation

Algorithm

Создайте хеш-таблицу counts, которая будет записывать частоту каждого символа в chars. Инициализируйте переменную ans = 0.

Итерируйте по каждому слову в words. Создайте хеш-таблицу wordCount, которая будет записывать частоту каждого символа в слове. Установите good = true. Итерируйте по каждому ключу c в wordCount. Пусть freq = wordCount[c]. Если counts[c] < freq, установите good = false и прервите цикл.

Если good = true, добавьте длину слова к ans. Верните ans.

😎