Guess the Word

XXX. Guess the Word

String

Greedy

Hash Table

Problem Statement:

You are given an API Master with a method int guess(String word). This method returns the number of exact matches of letters between your guess and the secret word. The goal is to find the secret word within 10 guesses.

Approach:

1. For each word in the wordlist, calculate how many other words have no matching characters (match == 0).
2. Choose the word with the fewest such matches as your next guess. This is a heuristic to minimize the worst-case scenario.
3. After each guess, filter the wordlist to only include words that match the number of matching characters returned by Master.guess().
4. Repeat the process until the secret word is found or you exhaust the 10 guesses.

Algorithm Intuition:

The key intuition behind the algorithm is to use the process of elimination efficiently:

• Choosing the next guess: By picking a word with the fewest mismatched pairs, we maximize the likelihood of reducing the wordlist significantly after each guess.
• Filtering the wordlist: After each guess, we retain only those words in the wordlist that have the same number of matches as returned by Master.guess(). This ensures we focus only on potential candidates for the secret word.
• Greedy heuristic: The algorithm greedily attempts to minimize the worst-case number of guesses by focusing on words with the smallest overlap in mismatched pairs.

Complexity:

Time Complexity: O(n²), where n is the number of words in the wordlist, due to pairwise comparisons.
Space Complexity: O(n), for maintaining the filtered wordlist and count mappings.

Java Implementation:

class Solution {
    public void findSecretWord(String[] wordlist, Master master) {
        for (int i = 0, x = 0; i < 10 && x < 6; ++i) {
            // Count the number of words that have no matching characters
            HashMap count = new HashMap<>();
            for (String w1 : wordlist)
                for (String w2 : wordlist)
                    if (match(w1, w2) == 0)
                        count.put(w1, count.getOrDefault(w1 , 0) + 1);

            // Choose the word with the fewest mismatches as the next guess
            String guess = "";
            int min0 = 100;
            for (String w : wordlist)
                if (count.getOrDefault(w, 0) < min0) {
                    guess = w;
                    min0 = count.getOrDefault(w, 0);
                }

            // Make the guess and get the number of matching characters
            x = master.guess(guess);

            // Filter the wordlist to only include words that match the number of matching characters
            List wordlist2 = new ArrayList();
            for (String w : wordlist)
                if (match(guess, w) == x)
                    wordlist2.add(w);
            wordlist = wordlist2.toArray(new String[0]);
        }
    }
    
    // Function to calculate the number of matching characters between two words
    public int match(String a, String b) {
        int matches = 0;
        for (int i = 0; i < a.length(); ++i)
            if (a.charAt(i) == b.charAt(i))
                matches ++;
        return matches;
    }
}