Maximum Score Words Formed by Letters

https://leetcode.com/problems/maximum-score-words-formed-by-letters/

一道DFS题目

通过DFS求出所有组合中 和最大的组合

先用prefix提前求出每个word的score和counter

另外DFS过程中预先判断剪枝prune

if currScore + sum(word_scores[i:]) < self.maxScore:

另外在DFS recursion前判断Counter是否够用的条件

if not (word_counters[j] - cnt):

from collections import Counter
class Solution(object):
    def getScore(self,word,score):
        res = 0
        for i in word:
            res += score[ord(i)-ord("a")]
        return res
    
    
    def maxScoreWords(self, words, letters, score):
        """
        :type words: List[str]
        :type letters: List[str]
        :type score: List[int]
        :rtype: int
        """
        self.maxScore = 0
        counter = Counter(letters)
        word_scores = [self.getScore(word,score) for word in words]
        word_counters = [Counter(word) for word in words]
        def dfs(i,currScore,cnt):
            #tree pruning part
            if currScore + sum(word_scores[i:]) < self.maxScore:
                return
            self.maxScore = max(self.maxScore,currScore)
            for j,word in enumerate(words[i:],i):
                if not (word_counters[j] - cnt):
                    dfs(j+1,currScore + word_scores[j], Counter({k:v - word_counters[j].get(k,0) for k,v in cnt.items()}))