Guess the Word

Hard Arrays & Hashing Greedy Original on LeetCode

Reported atGoogle

Guess the Word is a hard arrays & hashing problem solved with the greedy pattern. The best approach, optimal (minimax guess), runs in O(G · n²) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (guess the first remaining candidate) up.

Problem

You are given a list words of distinct six-letter lowercase words. One of them is the hidden secret. You cannot read it, but you may call a provided function guess(word) (in Java it is inherited from the Master class), which returns how many positions of word hold the same letter as secret, or -1 once you have used up your calls.

You may call guess at most allowedGuesses times. Only guess words from the list. Return the secret word: your answer is accepted only if it is the secret and you never went over the limit. A good strategy needs far fewer calls than trying words one by one.

Examples

Example 1

Input
words = ["kettle","bottle","settle","little","rattle"], secret = "little", allowedGuesses = 10
Output
"little"
Why
guess("kettle") returns 4 (both end in "ttle"), so only bottle, little and rattle, which also share exactly 4 positions with kettle, stay possible. One or two more calls find "little".

Example 2

Input
words = ["planet","plates","palace","prince"], secret = "palace", allowedGuesses = 10
Output
"palace"
Why
Each answer from guess() rules out the words that would have produced a different count, so the secret is found well within 10 calls.

Constraints

  • 1 <= words.length <= 100
  • words[i].length == 6, lowercase English letters, all distinct.
  • secret is one of the words.
  • 10 <= allowedGuesses <= 30

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (guess the first remaining candidate)O(G · n)O(n)
Optimal (minimax guess)O(G · n²)O(n)

1Brute force (guess the first remaining candidate)

TimeO(G · n)Each of the G guesses filters the pool in O(n · 6).
SpaceO(n)The candidate pool.

Keep a pool of words that could still be the secret. Guess the first one; the reply k says the secret shares exactly k positions with it, so keep only the words that share exactly k positions with the guess. Repeat until a guess returns 6.

  1. candidates = all words.
  2. Take w = candidates[0] and call k = guess(w).
  3. If k == 6, return w.
  4. Keep only the words x with matches(x, w) == k (this also drops w itself).
  5. Repeat; return an empty string if the pool runs out.
class Solution extends Master {
    public String findSecretWord(String[] words) {
        List<String> candidates = new ArrayList<>(Arrays.asList(words));
        while (!candidates.isEmpty()) {
            String w = candidates.get(0);
            int k = guess(w);
            if (k == 6) return w;
            List<String> next = new ArrayList<>();
            for (String x : candidates) {
                if (matches(x, w) == k) next.add(x);
            }
            candidates = next;
        }
        return "";
    }

    private int matches(String a, String b) {
        int same = 0;
        for (int i = 0; i < 6; i++) if (a.charAt(i) == b.charAt(i)) same++;
        return same;
    }
}

2Optimal (minimax guess)

TimeO(G · n²)Each of the G guesses compares every pair of candidates (6 letters each).
SpaceO(n)The candidate pool and a 7-slot counter.

Same filtering, but choose the guess carefully. For each remaining candidate, split the pool into 7 groups by how many positions each word shares with it. Whatever the reply is, the next pool is one of those groups, so guess the candidate whose largest group is smallest. That guarantees the fastest worst-case shrink among candidate guesses.

  1. candidates = all words.
  2. For each candidate w, count how many candidates fall into each match count 0..6 and record the largest count.
  3. Guess the w with the smallest largest count (first one on ties); return it if guess(w) == 6.
  4. Keep only the candidates sharing exactly guess(w) positions with w, and repeat.
class Solution extends Master {
    public String findSecretWord(String[] words) {
        List<String> candidates = new ArrayList<>(Arrays.asList(words));
        while (!candidates.isEmpty()) {
            String best = candidates.get(0);
            int bestWorst = Integer.MAX_VALUE;
            for (String w : candidates) {
                int[] groups = new int[7];
                for (String x : candidates) groups[matches(w, x)]++;
                int worst = 0;
                for (int g : groups) worst = Math.max(worst, g);
                if (worst < bestWorst) {
                    bestWorst = worst;
                    best = w;
                }
            }
            int k = guess(best);
            if (k == 6) return best;
            List<String> next = new ArrayList<>();
            for (String x : candidates) {
                if (matches(x, best) == k) next.add(x);
            }
            candidates = next;
        }
        return "";
    }

    private int matches(String a, String b) {
        int same = 0;
        for (int i = 0; i < 6; i++) if (a.charAt(i) == b.charAt(i)) same++;
        return same;
    }
}

Edge cases to test

  • A single word: one guess is enough
  • Words that differ in only one position, so every wrong guess returns 5 and removes only itself
  • Random words where most pairs share 0 letters

Hints

Hint 1

After guess(w) returns k, the secret must share exactly k positions with w. Every word that does not can be thrown away.

Hint 2

Always guessing a word that is still possible is already much better than guessing in list order.

Hint 3

To shrink the pool fastest, pick the candidate whose worst-case group (words sharing the same match count with it) is smallest.

FAQ

What is the best time complexity for Guess the Word?

Optimal (minimax guess) runs in O(G · n²) time and O(n) extra space. Each of the G guesses compares every pair of candidates (6 letters each).

Which pattern does Guess the Word use?

It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.

Is there a brute force solution for Guess the Word?

Yes. Brute force (guess the first remaining candidate) takes O(G · n) time and O(n) space. Keep a pool of words that could still be the secret.

Which edge cases should I test for Guess the Word?

A single word: one guess is enough; Words that differ in only one position, so every wrong guess returns 5 and removes only itself; Random words where most pairs share 0 letters.