thảo luận Leetcode mỗi ngày

function maxScoreWords(words: string[], letters: string[], score: number[]): number {
    const counts = new Array(26).fill(0);
    for (const letter of letters) counts[letter.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    const backtrack = (idx: number) => {
        let max = 0;
        for (let i = idx; i < words.length; i++) {
            let ans = 0, isGood = true;
            for (const c of words[i]) {
                counts[c.charCodeAt(0) - 'a'.charCodeAt(0)]--;
                ans+= score[c.charCodeAt(0) - 'a'.charCodeAt(0)];
                if (counts[c.charCodeAt(0) - 'a'.charCodeAt(0)] < 0) isGood = false;
            }
            if (isGood) {
                ans+= backtrack(i + 1);
                max = Math.max(ans, max);
            }
            for (const c of words[i]) {
                counts[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
                ans = 0;
            }
        }
        return max;
    }
    return backtrack(0);
};

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        d = Counter(letters)         
        def dfs(idx = 0, c = Counter()):
            if c - d:
                return 0
            if idx == len(words):
                return sum(v*score[ord(k) - ord('a')] for k, v in c.items())
            return max(dfs(idx + 1, c + Counter(words[idx])), dfs(idx + 1, c))
        return dfs()

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        self.result = 0
        letters_map = defaultdict(int)
        n = len(words)
        for letter in letters:
            letters_map[letter] += 1

        def getScore(word):
            s = 0
            for c in word:
                s += score[ord(c) - ord('a')]
            return s

        def canFormed(word):
            char_map = defaultdict(int)
            for c in word:
                char_map[c] += 1
                if char_map[c] > letters_map[c]:
                    return False
            return True

        def backtracking(i, current_score):
            if i == n:
                return
            
            if canFormed(words[i]):
                new_score = current_score + getScore(words[i])
                self.result = max(self.result, new_score)
                for c in words[i]:
                    letters_map[c] -= 1
                backtracking(i+1, new_score)
                for c in words[i]:
                    letters_map[c] += 1
            backtracking(i+1, current_score)
        
        backtracking(0, 0)
        return self.result

    func maxScoreWords(_ words: [String], _ letters: [Character], _ score: [Int]) -> Int {
        
        var res = 0

        func scoreChar(_ char: Character) -> Int {
            let index = Int(char.asciiValue!) - 97
            return score[index]
        }

        let maxChars = Dictionary(grouping: letters, by: {$0}).mapValues { $0.count * scoreChar($0[0]) }

        var arrayDfs: [String] = []
        func dfs(i: Int, s: Int, d: [Character: Int]) {
            guard i < words.count else {
                res = max(res, s)
                return
            }
            //
            let newWord = words[i]
            var newDict = d
            var newS = 0
            for char in [Character](newWord) {
                let charScore = scoreChar(char)
                newDict[char] = (newDict[char] ?? 0) + charScore
                newS += charScore
            }
            var isValid = true
            for (char, count) in newDict {
                if (maxChars[char] ?? Int.min) < count {
                    isValid = false
                    break
                }
            }
            //
            if isValid {
                arrayDfs.append(newWord)
                dfs(i: i+1, s:newS + s, d: newDict)
                arrayDfs.removeLast()
            }
            dfs(i: i+1, s:s, d: d)
        }

        dfs(i: 0, s:0, d: [:])

        return res
    }

public class Solution {
    public int CalculateScore(string[] words)
    {
        int result = 0;
        int tempScore = 0;
        bool isValid = true;
        Dictionary<char, int> tempLettersCount = new Dictionary<char, int>();
        tempLettersCount = lettersCount.ToDictionary(entry => entry.Key,
                                                     entry => entry.Value);
        foreach(string word in words)
        {
            for(int i = 0; i<word.Length; i++)
            {
                if(tempLettersCount.ContainsKey(word[i]))
                {
                    int temp = tempLettersCount[word[i]];
                    if(temp > 0)
                    {
                        tempScore += lettersScore[word[i]];
                        temp--;
                        tempLettersCount.Remove(word[i]);
                        tempLettersCount.Add(word[i], temp);
                    }
                    else
                    {
                        isValid = false;
                    }
                }
                else
                {
                    isValid = false;
                }
            }
            if(isValid)
            {
                result += tempScore;
            }
            tempScore = 0;
            isValid = true;
        }
        return result;
    }

    public void BackTrack(string[] words, int index, List<string> tempWords)
    {
        for(int i = index; i<words.Length; i++)
        {
            tempWords.Add(words[i]);
            int temp = CalculateScore(tempWords.ToArray());
            if(temp > result)
                result = temp;
            BackTrack(words, i+1, tempWords);
            tempWords.RemoveAt(tempWords.Count - 1);
        }
    }

    public static int result = 0;
    public static Dictionary<char, int> lettersCount;
    public static Dictionary<char, int> lettersScore;

    public int MaxScoreWords(string[] words, char[] letters, int[] score) {
        lettersCount = new Dictionary<char, int>();
        for(int i = 0; i<letters.Length; i++)
        {
            if(lettersCount.ContainsKey(letters[i]))
            {
                var temp = lettersCount[letters[i]];
                temp++;
                lettersCount.Remove(letters[i]);
                lettersCount.Add(letters[i], temp);
            }
            else
            {
                lettersCount.Add(letters[i], 1);
            }
        }

        lettersScore = new Dictionary<char, int>();
        for(int i = 0; i<26; i++)
        {
            lettersScore.Add((char)(97+i), score[i]);
        }
        
        List<string> tempWords = new List<string>();

        result = 0;
        BackTrack(words, 0, tempWords);

        return result;
    }
}

var maxScoreWords = function(words, letters, score) {
    const counts = {};
    for (const c of letters) {
        counts[c] = (counts[c] || 0) + 1;
    }

    const backtrack = (i, curScore, used) => {
        if (i === words.length) {
            res = Math.max(res, curScore);
            return;
        }

        // Skip this word
        backtrack(i + 1, curScore);

        // Include this word
        let wordScore = 0;
        let flag = true;

        for (const c of words[i]) {
            counts[c] = (counts[c] || 0) - 1;
            wordScore += score[c.charCodeAt(0) - 97];
            if (counts[c] < 0) {
                flag = false;
            }
        }
        
        if (flag) {
            backtrack(i + 1, curScore + wordScore);
        }

        // backtrack
        for (const c of words[i]) {
            counts[c] += 1;
        }
    }

    let res = 0;
    backtrack(0, 0);
    return res;
};

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        def calculateScore(wordCounter):
            return sum(count * score[ord(char) - ord('a')] for char, count in wordCounter.items())
        def backtrack(i):
            nonlocal charCounts
            if i == n:
                return 0 
    
            notTake = backtrack(i + 1)
            take = 0 
            if all(wordCharCount <= charCounts[char] for char, wordCharCount in wordCounters[i].items()):
                charCounts -= wordCounters[i]
                take = wordScores[i] + backtrack(i + 1)
                charCounts += wordCounters[i]
            return max(notTake, take)

        n = len(words)
        charCounts = Counter(letters)
        wordCounters = list(map(Counter, sorted(words, key=len, reverse=True)))
        wordScores = list(map(calculateScore, wordCounters))
        
        return backtrack(0)

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        hash_letters = {}
        for letter in letters:
            hash_letters[letter] = hash_letters.get(letter, 0) + 1
        words_letter = []
        words_score = []
        for word in words:
            word_letter = {}
            word_score = 0
            for char in word:
                word_letter[char] = word_letter.get(char, 0) + 1
                word_score += score[ord(char) - ord('a')]
            words_letter.append(word_letter)
            words_score.append(word_score)
        
        def maxScoreInner(hash_letters, words, words_score, words_letter, idx):
            if idx >= len(words):
                return 0
            valid = True
            for key in words_letter[idx]:
                valid = valid and words_letter[idx][key] <= hash_letters.get(key, 0)
            max_score = 0
            if valid:
                for key in words_letter[idx]:
                    hash_letters[key] -= words_letter[idx][key]
                max_score = max(max_score, words_score[idx] + maxScoreInner(hash_letters, words, words_score, words_letter, idx+1))
                for key in words_letter[idx]:
                    hash_letters[key] += words_letter[idx][key]
            return max(max_score, maxScoreInner(hash_letters, words, words_score, words_letter, idx+1))

        return maxScoreInner(hash_letters, words, words_score, words_letter, 0)

template<typename Arg, typename... Args>
void Log(Arg&& arg, Args&&... args)
{
    std::ostringstream oss;
    oss << std::boolalpha;
    oss << std::forward<Arg>(arg);
    ((oss << " " << std::forward<Args>(args)), ...);
    std::cout << oss.str() << "\n";
}

template<typename Arg, typename Iter>
void Log_c(Arg&& arg, Iter first, Iter last)
{
    std::ostringstream oss;
    oss << std::boolalpha;
    oss << std::forward<Arg>(arg);
    
    while (first != last)
    {
        oss << " " << *first;
        first++;
    }

    std::cout << oss.str() << "\n";
}

class Solution {
public:
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score)
    {
        std::vector<int> char_count(128, -1000000000);
        m_sz = words.size();

        for (const auto w : letters)
        {
            if (char_count[w] == -1000000000)
            {
                char_count[w] = 1;
            }
            else
            {
                char_count[w]++;
            }
        }

        int result{};
        dfs(char_count, score, words, 0, result);
        return m_result;
    }

private:
    int m_sz{};
    int m_result{};

    void dfs(std::vector<int>& char_count, const std::vector<int>& char_score, const std::vector<std::string>& words, int pos, int& result)
    {
        // Log("cur result", result, pos);
        if (pos >= m_sz)
        {
            m_result = std::max(m_result, result);
        }

        for (int cur_pos = pos; cur_pos < m_sz; ++cur_pos)
        {
            if (auto val = check(char_count, char_score, words[cur_pos]); val >= 0)
            {
                result += val;
                dfs(char_count, char_score, words, cur_pos + 1, result);
                result -= val;
                clear(char_count, words[cur_pos]);
            }
            else
            {
                // Log("check fail", pos, m_sz);
                dfs(char_count, char_score, words, cur_pos + 1, result);
            }
        }
    }

    int check(std::vector<int>& char_count, const std::vector<int>& char_score, const std::string& word)
    {
        bool st{true};
        int res{};
        for (int c : word)
        {
            // Log("char", c, char_count[c]);
            if (char_count[c] <= 0)
            {
                st = false;
            }
            else
            {
                res += char_score[c - 'a'];
            }

            char_count[c]--;
        }

        // Log("check", word, "score", res);
        if (st == false)
        {
            clear(char_count, word);
            return -1;
        }

        return res;
    }

    void clear(std::vector<int>& char_count, const std::string& word)
    {
        for (char c : word)
        {
            char_count[c]++;
        }
    }
};

class Solution {
    int ans;
    int n;
    int[] freq;
    
    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        ans = 0;
        n = words.length;
        freq = new int[26];
        for (char c: letters) {
            freq[c - 'a']++;
        }

        Map<String, Integer> wordScore = new HashMap<>();

        for (String word: words) {
            int s = 0;
            for (int i = 0; i < word.length(); i++) {
                s += score[word.charAt(i) - 'a'];
            }

            wordScore.put(word, s);
        }

        backtrack(0, 0, wordScore, words);

        return ans;
    }

    private void backtrack(int pos, int score, Map<String, Integer> wordScore, String[] words) {
        ans = Math.max(ans, score);

        if (pos == n) {
            return;
        }

        String word = words[pos];
        
        if (isPossibleToBuildWord(word)) {
            buildWord(word);
            backtrack(pos + 1, score + wordScore.get(word), wordScore, words);
            decompositeWord(word);
            backtrack(pos + 1, score, wordScore, words);
        } else {
            backtrack(pos + 1, score, wordScore, words);
        }

    }

    private boolean isPossibleToBuildWord(String word) {
        int[] wf = new int[26];

        for (int i = 0; i < word.length(); i++) {
            wf[word.charAt(i) - 'a']++;
        }

        for (int i = 0; i < 26; i++) {
            if (freq[i] < wf[i]) return false;
        }

        return true;
    }

    private void buildWord(String word) {
        for (int i = 0; i < word.length(); i++) {
            freq[word.charAt(i) - 'a']--;
        }
    }

    private void decompositeWord(String word) {
        for (int i = 0; i < word.length(); i++) {
            freq[word.charAt(i) - 'a']++;
        }
    }

}