Problem Statement |
| | You are playing a game that borrows principles from the popular games Scrabble and Wheel of Fortune. The game board consists of one or more words, all of which are completely hidden at the very beginning. You have a pool of letters, and you select one letter at a time. Each time you select a letter, all instances of that letter will be revealed on the board. The goal of the game is to accurately guess all the words.
You are given a String pool and a String[] board. pool contains all the letters in your pool and board contains all the words on the board. You are also given an int threshold. When the total number of hidden letters on the board is less than or equal to threshold, you will be able to accurately guess all the words and win. The total number of hidden letters includes all occurrences of letters, not just distinct letters. For example, if the hidden letters are "aaab", the total number of hidden letters is 4.
Your goal is to win the game by selecting the minimum possible number of letters from your pool. Return a String containing the letters you should choose (all lowercase). If there are multiple solutions, return the one that comes first alphabetically. If it is impossible to win, return "IMPOSSIBLE" (quotes for clarity).
|
| |
Definition |
| | | Class: | ScrabFortune | | Method: | getMin | | Parameters: | String, String[], int | | Returns: | String | | Method signature: | String getMin(String pool, String[] board, int threshold) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The letters in pool may or may not be distinct. |
| |
Constraints |
| - | pool will contain between 1 and 50 lowercase letters ('a'-'z'), inclusive. |
| - | board will contain between 1 and 50 elements, inclusive. |
| - | Each element of board will contain between 1 and 50 lowercase letters ('a'-'z'), inclusive. |
| - | threshold will be between 0 and 2500, inclusive. |
| |
Examples |
| 0) | |
| | "fpsctyba" | {"scrab",
"fortune",
"is",
"fun"} | 10 |
| Returns: "abcfs" | | Using the letters a, b, and c reveals a total of 3 letters in the board. Now, if we choose f and s, we reveal 4 more letters, for a total of 7. Since exactly 10 hidden letters remain, the game is won. |
|
|
| 1) | |
| | "lllllo" | {"hello",
"world"} | 6 |
| Returns: "lo" | | Watch out for multiple occurrences of the same letter in pool. |
|
|
| 2) | |
| | "l" | {"blbvbvb",
"ajllkjk",
"bjkdfle"} | 16 |
| Returns: "IMPOSSIBLE" | |
|
| 3) | |
| | |
| 4) | |
| | "tkse" | {
"easy",
"to",
"solve"} | 600 |
| Returns: "" | | You can win the game without selecting any letters. |
|
|