The Word Crush puzzle gives you a collection of words wordbank and a target word

Question

The Word Crush puzzle gives you a collection of words wordbank and a target word goal and asks you to find the fewest words from wordbank whose letters can be rearranged to form goal. Give pseudocode for a greedy solution to the Word Crush puzzle.
For example, if your word bank was {exhaustive, search, brute, force, divide, and, conquer, dynamic, programming, greedy, algorithm} and your goal was beautiful, the optimal solution would be {brute, force, algorithm}.
The Word Crush puzzle gives you a collection of words wordbank and a target word goal and asks you to find the fewest words from wordbank whose letters can be rearranged to form goal. Give pseudocode for a greedy solution to the Word Crush puzzle.
For example, if your word bank was {exhaustive, search, brute, force, divide, and, conquer, dynamic, programming, greedy, algorithm} and your goal was beautiful, the optimal solution would be {brute, force, algorithm}.
The Word Crush puzzle gives you a collection of words wordbank and a target word goal and asks you to find the fewest words from wordbank whose letters can be rearranged to form goal. Give pseudocode for a greedy solution to the Word Crush puzzle.
For example, if your word bank was {exhaustive, search, brute, force, divide, and, conquer, dynamic, programming, greedy, algorithm} and your goal was beautiful, the optimal solution would be {brute, force, algorithm}.
The Word Crush puzzle gives you a collection of words wordbank and a target word goal and asks you to find the fewest words from wordbank whose letters can be rearranged to form goal. Give pseudocode for a greedy solution to the Word Crush puzzle.
For example, if your word bank was {exhaustive, search, brute, force, divide, and, conquer, dynamic, programming, greedy, algorithm} and your goal was beautiful, the optimal solution would be {brute, force, algorithm}.

Explanation / Answer

Step 1: Arrange the words wordsbank with respect to variety of letters in the word that matches letters in goal. e.g. with goal set to orange, word 'change' comes before 'balloon' since 'change' has 4 distinct characters whereas 'balloon' has only 2 distinct characters that match characters 'orange'.

Step 2: Add the first word from the wordbank, and remove the word from wordbank and mark all the letters in goal that are present in the word we selected from wordbank .

Step 3: We now check if any letter in goal is still unmarked, if so we proceed to step 3 else stop here

Step 4: We check if there is any character from the first available word in the wordlist matches unmarked characters of goal. If matches go to step 2. Else we remove the first word from wordlist and repeat step 3, unless the wordbank is exhausted.

NOTE: After step 2 we can again re-arrange the words in wordbank based on the unmarked charachters of goal. But sometimes people refer rearranging not greedy, so I omitted that step.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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