[Leetcode] 1255. Maximum Score Words Formed by Letters - Python, Backtrack

접근

1. 백트래킹

난이도가 Hard이나 전형적인 탐색 문제라 접근이 쉬운 편이다(Middle 상위보다 쉬움) BFS보다 백트래킹이 메모리 효율성이 좋을 것 같다.

풀이

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        
        answer = 0
        N = len(words)
        dict_ = defaultdict(lambda:[0, 0])

        for ch in letters:
            dict_[ch][0] += 1
            dict_[ch][1] = score[ord(ch)-97]
        
        # print(dict_.items())

        def backtrack(idx, ans):
            nonlocal answer, dict_
            if idx == N:
                answer = max(answer, ans)
                return
            
            backtrack(idx+1, ans)

            flag, temp = True, 0
            for ch in words[idx]:
                if dict_[ch][0] <= 0:
                    flag = False
                dict_[ch][0] -= 1
                temp += dict_[ch][1]
            
            if flag:
                backtrack(idx+1, ans+temp)

            for ch in words[idx]:
                dict_[ch][0] += 1

            return
        
        backtrack(0, 0)
        return answer