Space
Open
From Fieldwork
Scales
Archive
This problem is a variation of the Knapsack Problem or the Subset Sum Problem, but with character frequency constraints. Since the number of words is relatively small, we can solve it using Backtracking or Bitmasking to explore all possible subsets of words.
For each word, we have two choices:
Skip the word: Move to the next word without using any letters.
Use the word: Check if we have enough characters in our letters supply. If we do, subtract them, add the word's score, and recurse. We "undo" the subtraction (backtrack) after the recursive call.
class Solution:
def maxScoreWords(self, words, letters, score):
# 1. Count our available resources
letter_counts = Counter(letters)
def get_word_score(word):
"""Helper to calculate score of a word; returns 0 if impossible."""
s = 0
for char in word:
s += score[ord(char) - ord('a')]
return s
def can_form(word, current_counts):
"""Check if we have enough letters left to form the word."""
word_counts = Counter(word)
for char, count in word_counts.items():
if current_counts[char] < count:
return False
return True
def backtrack(index, current_counts):
if index == len(words):
return 0
# Option 1: Skip the current word
max_s = backtrack(index + 1, current_counts)
# Option 2: Try to take the current word
word = words[index]
if can_form(word, current_counts):
# "Pay" the letters
for char in word:
current_counts[char] -= 1
# Add word score + recurse
take_score = get_word_score(word) + backtrack(index + 1, current_counts)
max_s = max(max_s, take_score)
# "Backtrack": Put the letters back for other branches
for char in word:
current_counts[char] += 1
return max_s
return backtrack(0, letter_counts)Practice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode