LeetCode 843: Guess the Word

Problem Restatement

We are given a list of unique strings words.

Each word has length 6.

One word from the list is chosen as the secret word.

We can call:

master.guess(word)

This returns:

We must find the secret word within at most 10 guesses. This is an interactive problem, so the function does not return the secret word. It calls master.guess until the secret is found.

Input and Output

Function shape:

class Solution:
    def findSecretWord(self, words: list[str], master: 'Master') -> None:
        ...

Examples

Suppose:

secret = "acckzz"
words = ["acckzz", "ccbazz", "eiowzz", "abcczz"]

If we guess:

"ccbazz"

Compare it with the secret:

secret: acckzz
guess:  ccbazz

Matching positions are:

So:

master.guess("ccbazz") == 3

This tells us that the secret must be one of the remaining words that has exactly 3 matching positions with "ccbazz".

First Thought: Random Guess and Filter

A simple strategy is:

1. Pick any word from the current candidate list.
2. Call master.guess(word).
3. Suppose the result is matches.
4. Keep only words that have exactly matches matching positions with the guessed word.
5. Repeat.

This works because the secret must be consistent with every feedback result.

class Solution:
    def findSecretWord(self, words: list[str], master: 'Master') -> None:
        def match(a: str, b: str) -> int:
            return sum(x == y for x, y in zip(a, b))

        candidates = words[:]

        for _ in range(10):
            guess = candidates[0]
            score = master.guess(guess)

            if score == 6:
                return

            candidates = [
                word
                for word in candidates
                if match(word, guess) == score
            ]

This filtering idea is the core of the solution.

But choosing the first candidate can be weak. We want guesses that reduce the candidate list quickly.

Key Insight

Every guess partitions the candidate list into groups by match count.

For a guess word, each remaining candidate would produce a score from 0 to 6.

A good guess has no very large group after partitioning, because no matter what score comes back, the remaining candidate list becomes small.

So we can choose the word with the best worst-case split.

For each possible guess:

1. Count how many candidates give score 0, score 1, …, score 6.
2. Let the largest bucket size be the worst case.
3. Pick the guess with the smallest worst-case bucket.

This is a minimax-style heuristic.

Algorithm

Use a helper function:

match(a, b)

which returns the number of equal characters at the same positions.

Then repeat up to 10 times:

1. Choose a guess from the current candidate list.
2. Use minimax bucket scoring to choose a strong guess.
3. Call master.guess(guess).
4. If the result is 6, the secret is found.
5. Otherwise, filter candidates to only words with the same match count against the guess.

Walkthrough

Suppose the current candidates are:

["acckzz", "ccbazz", "eiowzz", "abcczz"]

Guess:

"ccbazz"

The result is:

3

Now we keep only words that have exactly 3 matches with "ccbazz".

Compare:

The new candidates are:

["acckzz", "abcczz"]

The secret must be one of these.

If we later guess "acckzz" and get 6, the secret is found.

Correctness

After each guess, master.guess(guess) returns the number of exact position matches between the guess and the secret.

Any word that does not have this same match count against the guess cannot be the secret, because it would have produced different feedback.

Any word that does have the same match count remains possible, because it is still consistent with all feedback seen so far.

Therefore, the filtering step never removes the true secret and removes only impossible candidates.

If the algorithm receives score 6, the guessed word matches the secret at all six positions. Since all words have length 6, the guessed word is the secret.

The minimax selection affects efficiency, not validity. The correctness comes from always guessing a word from the candidate list and filtering by exact feedback consistency.

Complexity

Let:

n = len(words)

Each word has fixed length 6.

Since word length is fixed at 6, each match check is constant time.

Implementation

from collections import Counter

class Solution:
    def findSecretWord(self, words: list[str], master: 'Master') -> None:
        def match(a: str, b: str) -> int:
            count = 0

            for x, y in zip(a, b):
                if x == y:
                    count += 1

            return count

        def choose_guess(candidates: list[str]) -> str:
            best_word = candidates[0]
            best_worst_group = len(candidates)

            for guess in candidates:
                buckets = Counter()

                for word in candidates:
                    if word != guess:
                        buckets[match(guess, word)] += 1

                worst_group = max(buckets.values(), default=0)

                if worst_group < best_worst_group:
                    best_worst_group = worst_group
                    best_word = guess

            return best_word

        candidates = words[:]

        for _ in range(10):
            guess = choose_guess(candidates)
            score = master.guess(guess)

            if score == 6:
                return

            candidates = [
                word
                for word in candidates
                if match(word, guess) == score
            ]

Code Explanation

The match helper counts exact-position matches:

def match(a: str, b: str) -> int:

For example:

match("ccbazz", "acckzz") == 3

The choose_guess helper selects the candidate with the smallest worst-case bucket:

def choose_guess(candidates: list[str]) -> str:

For each guess, it groups all candidates by the score they would return:

buckets[match(guess, word)] += 1

Then it measures the worst remaining group:

worst_group = max(buckets.values(), default=0)

The smallest worst group is preferred.

After guessing:

score = master.guess(guess)

a score of 6 means the secret has been found:

if score == 6:
    return

Otherwise, filter to candidates consistent with the feedback:

candidates = [
    word
    for word in candidates
    if match(word, guess) == score
]

Testing

Interactive LeetCode problems cannot be tested with a normal return value, but we can create a local Master mock.

class Master:
    def __init__(self, secret: str, words: list[str]):
        self.secret = secret
        self.words = set(words)
        self.calls = 0
        self.found = False

    def guess(self, word: str) -> int:
        self.calls += 1

        if word not in self.words:
            return -1

        score = sum(a == b for a, b in zip(word, self.secret))

        if score == 6:
            self.found = True

        return score

def run_tests():
    words = ["acckzz", "ccbazz", "eiowzz", "abcczz"]
    master = Master("acckzz", words)

    Solution().findSecretWord(words, master)

    assert master.found is True
    assert master.calls <= 10

    words = [
        "abcdef",
        "abqdef",
        "zzzzzz",
        "abcxyz",
        "axcyef",
        "mnopqr",
    ]
    master = Master("abqdef", words)

    Solution().findSecretWord(words, master)

    assert master.found is True
    assert master.calls <= 10

    print("all tests passed")

run_tests()

Test meaning: