Scrabble: We\'re given a dictionary of n strings, each with length L characters.

Question

Scrabble: We're given a dictionary of n strings, each with length L characters. Eachstring in the dictionary has an associated number of points. We're also given a set of available characters S (which may include repeats). We'd like to determine if we can select at most k strings from the dictionary which can be simultaneously constructed from S and are worth at least P points total. For example, we may have characters S = A; A;C;C;R; T. We can form CAT and CAR simultaneously, but we cannot form CAT and RAT simultaneously (because there is only one T). Either prove that this problem is NP-Complete, or give a polynomial-time solution.

Explanation / Answer

Please rate me 5 star pleaseeeeeeeeeeee (I would like to help you in anyway related to algorithms)
We can consider this problem as Anagram solver.So lets prove that Anagram solving is NP complete:

f you'd prove that solving anagram finding (not more than polynomial number of times) solves subset sum problem - it would be a revolution in computer science (you'd prove P=NP).

Clearly finding anagrams is polynomial-time problem:

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.