Hard

题目描述

给定一个由唯一字符串组成的数组 words，其中 words[i] 是长度为六的字符串。words 中的一个单词被选作秘密单词。

你还会得到一个辅助对象 Master。你可以调用 Master.guess(word)，其中 word 是一个长度为六的字符串，并且必须是来自 words 的。Master.guess(word) 返回：

  • 如果 word 不在 words 中，返回 -1
  • 一个整数，表示你的猜测与秘密单词的精确匹配数（值和位置都匹配）

每个测试用例都有一个参数 allowedGuesses，表示你最多可以调用 Master.guess(word) 的次数。

对于每个测试用例，你应该在不超过最大允许猜测次数的情况下调用 Master.guess 猜出秘密单词。你会得到：

  • 如果你调用 Master.guess 的次数超过 allowedGuesses 次或者你没有猜出秘密单词，返回 “Either you took too many guesses, or you did not find the secret word.”
  • 如果你在调用 Master.guess 次数小于或等于 allowedGuesses 的情况下猜出了秘密单词，返回 “You guessed the secret word correctly.”

测试用例保证你可以用合理的策略（而不是暴力方法）猜出秘密单词。

示例 1：

输入：secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10
输出：You guessed the secret word correctly.
解释：
master.guess("aaaaaa") 返回 -1，因为 "aaaaaa" 不在 words 中。
master.guess("acckzz") 返回 6，因为 "acckzz" 是秘密单词，有 6 个匹配。
master.guess("ccbazz") 返回 3，因为 "ccbazz" 有 3 个匹配。
master.guess("eiowzz") 返回 2，因为 "eiowzz" 有 2 个匹配。
master.guess("abcczz") 返回 4，因为 "abcczz" 有 4 个匹配。
我们调用了 5 次 master.guess，其中一次是秘密单词，所以通过测试用例。

示例 2：

输入：secret = "hamada", words = ["hamada","khaled"], allowedGuesses = 10
输出：You guessed the secret word correctly.
解释：因为有两个单词，你可以猜测两个。

提示：

  • 1 <= words.length <= 100
  • words[i].length == 6
  • words[i] 由小写英文字母组成
  • words 的所有字符串都是唯一的
  • secret 存在于 words 中
  • 10 <= allowedGuesses <= 30

解题思路

这是一道交互式题目，需要设计策略在有限次数内猜出秘密单词。关键思路是利用每次猜测的返回值来缩小候选范围。

核心策略：

  1. 随机选择策略：从当前候选单词中随机选择一个进行猜测
  2. 根据匹配数过滤：如果猜测单词与秘密单词有 k 个位置匹配，那么真正的秘密单词与这个猜测单词也必须有 k 个位置匹配
  3. 缩小候选范围：每次猜测后，保留那些与猜测单词有相同匹配数的候选单词

优化策略：

  • 最小化最坏情况：选择能使候选集合分割最均匀的单词
  • 避免相似单词：优先选择与已有候选单词差异较大的单词

算法流程：

  1. 维护一个候选单词列表，初始为所有单词
  2. 从候选列表中选择一个单词进行猜测
  3. 根据返回的匹配数，过滤掉不符合条件的候选单词
  4. 重复步骤2-3，直到找到秘密单词或候选列表为空

这种策略的关键在于每次猜测都能显著减少候选范围，通常在10次以内就能找到答案。

代码实现

class Solution {
public:
    int getMatches(const string& word1, const string& word2) {
        int matches = 0;
        for (int i = 0; i < 6; i++) {
            if (word1[i] == word2[i]) {
                matches++;
            }
        }
        return matches;
    }
    
    void findSecretWord(vector<string>& words, Master& master) {
        vector<string> candidates = words;
        
        for (int attempt = 0; attempt < 10 && !candidates.empty(); attempt++) {
            // 随机选择一个候选单词
            int idx = rand() % candidates.size();
            string guess = candidates[idx];
            
            int matches = master.guess(guess);
            
            // 如果找到秘密单词，直接返回
            if (matches == 6) {
                return;
            }
            
            // 过滤候选单词，保留与guess有相同匹配数的单词
            vector<string> newCandidates;
            for (const string& word : candidates) {
                if (getMatches(word, guess) == matches) {
                    newCandidates.push_back(word);
                }
            }
            candidates = newCandidates;
        }
    }
};

class Solution:
    def findSecretWord(self, words: List[str], master: 'Master') -> None:
        import random
        
        def get_matches(word1, word2):
            return sum(c1 == c2 for c1, c2 in zip(word1, word2))
        
        candidates = words[:]
        
        for _ in range(10):
            if not candidates:
                break
                
            # 随机选择一个候选单词
            guess = random.choice(candidates)
            matches = master.guess(guess)
            
            # 如果找到秘密单词，直接返回
            if matches == 6:
                return
            
            # 过滤候选单词，保留与guess有相同匹配数的单词
            candidates = [word for word in candidates 
                         if get_matches(word, guess) == matches]

public class Solution {
    private int GetMatches(string word1, string word2) {
        int matches = 0;
        for (int i = 0; i < 6; i++) {
            if (word1[i] == word2[i]) {
                matches++;
            }
        }
        return matches;
    }
    
    public void FindSecretWord(string[] words, Master master) {
        var candidates = new List<string>(words);
        var random = new Random();
        
        for (int attempt = 0; attempt < 10 && candidates.Count > 0; attempt++) {
            // 随机选择一个候选单词
            int idx = random.Next(candidates.Count);
            string guess = candidates[idx];
            
            int matches = master.Guess(guess);
            
            // 如果找到秘密单词，直接返回
            if (matches == 6) {
                return;
            }
            
            // 过滤候选单词，保留与guess有相同匹配数的单词
            var newCandidates = new List<string>();
            foreach (string word in candidates) {
                if (GetMatches(word, guess) == matches) {
                    newCandidates.Add(word);
                }
            }
            candidates = newCandidates;
        }
    }
}

var findSecretWord = function(words, master) {
    function getMatches(word1, word2) {
        let matches = 0;
        for (let i = 0; i < 6; i++) {
            if (word1[i] === word2[i]) matches++;
        }
        return matches;
    }
    
    let candidates = [...words];
    
    for (let i = 0; i < 10; i++) {
        if (candidates.length === 0) break;
        
        // Choose word that minimizes worst case
        let bestWord = candidates[0];
        let minWorstCase = candidates.length;
        
        for (let word of candidates) {
            let groups = new Map();
            for (let candidate of candidates) {
                let matches = getMatches(word, candidate);
                groups.set(matches, (groups.get(matches) || 0) + 1);
            }
            
            let maxGroupSize = Math.max(...groups.values());
            if (maxGroupSize < minWorstCase) {
                minWorstCase = maxGroupSize;
                bestWord = word;
            }
        }
        
        let result = master.guess(bestWord);
        if (result === 6) return;
        
        candidates = candidates.filter(word => getMatches(bestWord, word) === result);
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(N × 6 × attempts)N为单词数量，每次比较需要O(6)，最多尝试10次
空间复杂度O(N)存储候选单词列表