第 86 場周賽：矩陣中的幻方、鑰匙和房間、將數組拆分成斐波那契序列、猜猜這個單詞

Q1、[中等] 矩陣中的幻方

1、題目描述

3 x 3 的幻方是一個填充有 從 1 到 9 的不同數字的 3 x 3 矩陣，其中每行，每列以及兩條對角線上的各數之和都相等。

給定一個由整數組成的row x col 的 grid，其中有多少個 3 × 3 的 “幻方” 子矩陣？

注意：雖然幻方只能包含 1 到 9 的數字，但 grid 可以包含最多15的數字。

示例 1：

輸入: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]
輸出: 1
解釋: 
下面的子矩陣是一個 3 x 3 的幻方：而這一個不是：總的來說，在本示例所給定的矩陣中只有一個 3 x 3 的幻方子矩陣。

示例 2:

輸入: grid = [[8]]
輸出: 0

提示:

row == grid.length
col == grid[i].length
1 <= row, col <= 10
0 <= grid[i][j] <= 15

2、解題思路

問題分析：
- 需要遍歷 grid 中所有可能的 3 × 3 子矩陣。
- 對于每個子矩陣，檢查它是否滿足幻方的條件。
幻方的條件：
- 包含 1 到 9 的不同數字。
- 每行、每列以及兩條對角線的和都等于 15。
優化：
- 幻方的中心必須是 5，因此可以提前過濾掉中心不是 5 的子矩陣。
算法設計：
- 遍歷 grid 中所有可能的 3 × 3 子矩陣。
- 對于每個子矩陣，檢查是否滿足幻方的條件。
- 統計滿足條件的子矩陣數量。

3、代碼實現

C++

class Solution {
public:// 檢查一個 3x3 矩陣是否是幻方bool ismagic(array<int, 9> m) {int count[16] = {0}; // 用于統計數字出現的次數for (auto n : m) {// 檢查數字是否在 1 到 9 之間且不重復if (n < 1 || n > 9 || ++count[n] > 1) {return false;}}// 檢查每行、每列以及兩條對角線的和是否等于 15return m[0] + m[1] + m[2] == 15 && m[3] + m[4] + m[5] == 15 &&m[6] + m[7] + m[8] == 15 && m[0] + m[3] + m[6] == 15 &&m[1] + m[4] + m[7] == 15 && m[2] + m[5] + m[8] == 15 &&m[0] + m[4] + m[8] == 15 && m[2] + m[4] + m[6] == 15;}int numMagicSquaresInside(vector<vector<int>>& grid) {if (grid.size() < 3 || grid[0].size() < 3) {return 0; // 如果 grid 的大小小于 3x3，直接返回 0}int m = grid.size(), n = grid[0].size();int res = 0;                           // 記錄幻方的數量for (int i = 0; i < m - 2; i++) {      // 遍歷所有可能的起始行for (int j = 0; j < n - 2; j++) {  // 遍歷所有可能的起始列if (grid[i + 1][j + 1] != 5) { // 如果中心不是 5，跳過continue;}array<int, 9> v; // 用于存儲 3x3 子矩陣的元素int w = 0;for (int r = i; r < i + 3; r++) { // 提取 3x3 子矩陣for (int c = j; c < j + 3; c++) {v[w++] = grid[r][c];}}res += ismagic(v); // 檢查是否是幻方}}return res; // 返回幻方的數量}
};

Java

class Solution {// 檢查一個 3x3 矩陣是否是幻方private boolean ismagic(int[] m) {int[] count = new int[16]; // 用于統計數字出現的次數for (int n : m) {if (n < 1 || n > 9 || ++count[n] > 1) { // 檢查數字是否在 1 到 9 之間且不重復return false;}}// 檢查每行、每列以及兩條對角線的和是否等于 15return  m[0] + m[1] + m[2] == 15 && m[3] + m[4] + m[5] == 15 &&m[6] + m[7] + m[8] == 15 && m[0] + m[3] + m[6] == 15 &&m[1] + m[4] + m[7] == 15 && m[2] + m[5] + m[8] == 15 &&m[0] + m[4] + m[8] == 15 && m[2] + m[4] + m[6] == 15;}public int numMagicSquaresInside(int[][] grid) {if (grid.length < 3 || grid[0].length < 3) {return 0; // 如果 grid 的大小小于 3x3，直接返回 0}int m = grid.length, n = grid[0].length;int res = 0; // 記錄幻方的數量for (int i = 0; i < m - 2; i++) { // 遍歷所有可能的起始行for (int j = 0; j < n - 2; j++) { // 遍歷所有可能的起始列if (grid[i + 1][j + 1] != 5) { // 如果中心不是 5，跳過continue;}int[] v = new int[9]; // 用于存儲 3x3 子矩陣的元素int w = 0;for (int r = i; r < i + 3; r++) { // 提取 3x3 子矩陣for (int c = j; c < j + 3; c++) {v[w++] = grid[r][c];}}res += ismagic(v) ? 1 : 0; // 檢查是否是幻方}}return res; // 返回幻方的數量}
}

Python

class Solution:def ismagic(self, m):count = [0] * 16  # 用于統計數字出現的次數for n in m:if n < 1 or n > 9 or count[n] > 0:  # 檢查數字是否在 1 到 9 之間且不重復return Falsecount[n] += 1# 檢查每行、每列以及兩條對角線的和是否等于 15return (m[0] + m[1] + m[2] == 15and m[3] + m[4] + m[5] == 15and m[6] + m[7] + m[8] == 15and m[0] + m[3] + m[6] == 15and m[1] + m[4] + m[7] == 15and m[2] + m[5] + m[8] == 15and m[0] + m[4] + m[8] == 15and m[2] + m[4] + m[6] == 15)def numMagicSquaresInside(self, grid):if len(grid) < 3 or len(grid[0]) < 3:return 0  # 如果 grid 的大小小于 3x3，直接返回 0m, n = len(grid), len(grid[0])res = 0  # 記錄幻方的數量for i in range(m - 2):  # 遍歷所有可能的起始行for j in range(n - 2):  # 遍歷所有可能的起始列if grid[i + 1][j + 1] != 5:  # 如果中心不是 5，跳過continuev = [grid[r][c] for r in range(i, i + 3) for c in range(j, j + 3)]  # 提取 3x3 子矩陣res += 1 if self.ismagic(v) else 0  # 檢查是否是幻方return res  # 返回幻方的數量

在這里插入圖片描述

4、復雜度分析

時間復雜度：
- 遍歷所有可能的 3 × 3 子矩陣：O((m?2)×(n?2))。
- 檢查每個子矩陣是否是幻方：O(1)。
- 總時間復雜度：O((m?2)×(n?2))。
空間復雜度：
- 使用常數級別的額外空間，空間復雜度為 O(1)。

Q2、[中等] 鑰匙和房間

1、題目描述

有 n 個房間，房間按從 0 到 n - 1 編號。最初，除 0 號房間外的其余所有房間都被鎖住。你的目標是進入所有的房間。然而，你不能在沒有獲得鑰匙的時候進入鎖住的房間。

當你進入一個房間，你可能會在里面找到一套 不同的鑰匙，每把鑰匙上都有對應的房間號，即表示鑰匙可以打開的房間。你可以拿上所有鑰匙去解鎖其他房間。

給你一個數組 rooms 其中 rooms[i] 是你進入 i 號房間可以獲得的鑰匙集合。如果能進入所有房間返回 true，否則返回 false。

示例 1：
輸入：rooms = [[1],[2],[3],[]]
輸出：true
解釋：
我們從 0 號房間開始，拿到鑰匙 1。
之后我們去 1 號房間，拿到鑰匙 2。
然后我們去 2 號房間，拿到鑰匙 3。
最后我們去了 3 號房間。
由于我們能夠進入每個房間，我們返回 true。
示例 2：
輸入：rooms = [[1,3],[3,0,1],[2],[0]]
輸出：false
解釋：我們不能進入 2 號房間。
提示：

n == rooms.length
2 <= n <= 1000
0 <= rooms[i].length <= 1000
1 <= sum(rooms[i].length) <= 3000
0 <= rooms[i][j] < n
所有 rooms[i] 的值 互不相同

2、解題思路

問題分析：
- 房間和鑰匙的關系可以看作是一個圖，其中房間是節點，鑰匙是邊。
- 從 0 號房間開始，通過鑰匙逐步解鎖其他房間。
- 需要判斷是否可以從 0 號房間訪問到所有其他房間。
算法設計：
- 使用廣度優先搜索（BFS）或深度優先搜索（DFS）遍歷圖。
- 從 0 號房間開始，將所有可以訪問的房間加入集合。
- 最終檢查集合的大小是否等于 n。
優化：
- 使用 BFS 或 DFS 確保所有可達房間都被訪問。

3、代碼實現

C++

class Solution {
public:bool canVisitAllRooms(vector<vector<int>>& rooms) {int n = rooms.size();       // 房間的數量unordered_set<int> visited; // 記錄已訪問的房間queue<int> q;               // BFS 隊列q.push(0);                  // 從 0 號房間開始visited.insert(0);          // 標記 0 號房間為已訪問while (!q.empty()) {       // BFS 過程int index = q.front(); // 取出當前房間q.pop();for (const auto& key : rooms[index]) { // 遍歷當前房間的鑰匙if (!visited.count(key)) {         // 如果鑰匙對應的房間未被訪問q.push(key);                   // 加入隊列visited.insert(key);           // 標記為已訪問}}}return visited.size() == n; // 判斷是否訪問了所有房間}
};

class Solution {
private:vector<int> visited;int num;void dfs(vector<vector<int>>& rooms, int x) {visited[x] = true;num++;for (const auto& it : rooms[x]) {if (!visited[it]) {dfs(rooms, it);}}}public:bool canVisitAllRooms(vector<vector<int>>& rooms) {int n = rooms.size();num = 0;visited.resize(n);dfs(rooms, 0);return num == n;}
};

Java

class Solution {public boolean canVisitAllRooms(List<List<Integer>> rooms) {int n = rooms.size(); // 房間的數量Set<Integer> visited = new HashSet<>(); // 記錄已訪問的房間Queue<Integer> q = new LinkedList<>(); // BFS 隊列q.offer(0); // 從 0 號房間開始visited.add(0); // 標記 0 號房間為已訪問while (!q.isEmpty()) { // BFS 過程int index = q.poll(); // 取出當前房間for (int key : rooms.get(index)) { // 遍歷當前房間的鑰匙if (!visited.contains(key)) { // 如果鑰匙對應的房間未被訪問q.offer(key); // 加入隊列visited.add(key); // 標記為已訪問}}}return visited.size() == n; // 判斷是否訪問了所有房間}
}

Python

class Solution:def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:n = len(rooms)  # 房間的數量visited = set()  # 記錄已訪問的房間q = deque()  # BFS 隊列q.append(0)  # 從 0 號房間開始visited.add(0)  # 標記 0 號房間為已訪問while q:  # BFS 過程index = q.popleft()  # 取出當前房間for key in rooms[index]:  # 遍歷當前房間的鑰匙if key not in visited:  # 如果鑰匙對應的房間未被訪問q.append(key)  # 加入隊列visited.add(key)  # 標記為已訪問return len(visited) == n  # 判斷是否訪問了所有房間

在這里插入圖片描述

4、復雜度分析

時間復雜度：
- 每個房間和鑰匙最多被訪問一次，時間復雜度為 O*(*n+k)，其中 n 是房間的數量，k 是鑰匙的總數。
空間復雜度：
- 使用 visited 集合和隊列 q，空間復雜度為 O(n)。

Q3、[中等] 將數組拆分成斐波那契序列

1、題目描述

給定一個數字字符串 num，比如 "123456579"，我們可以將它分成「斐波那契式」的序列 [123, 456, 579]。

形式上，斐波那契式 序列是一個非負整數列表 f，且滿足：

0 <= f[i] < 231 ，（也就是說，每個整數都符合 32 位 有符號整數類型）
f.length >= 3
對于所有的0 <= i < f.length - 2，都有 f[i] + f[i + 1] = f[i + 2]

另外，請注意，將字符串拆分成小塊時，每個塊的數字一定不要以零開頭，除非這個塊是數字 0 本身。

返回從 num 拆分出來的任意一組斐波那契式的序列塊，如果不能拆分則返回 []。

示例 1：

輸入：num = "1101111"
輸出：[11,0,11,11]
解釋：輸出 [110,1,111] 也可以。

示例 2：

輸入: num = "112358130"
輸出: []
解釋: 無法拆分。

示例 3：

輸入："0123"
輸出：[]
解釋：每個塊的數字不能以零開頭，因此 "01"，"2"，"3" 不是有效答案。

提示：

1 <= num.length <= 200
num 中只含有數字

2、解題思路

問題分析：
- 需要將字符串 num 拆分成一個斐波那契式序列。
- 序列中的每個整數必須滿足 0 <= f[i] < 2^31。
- 序列的長度至少為 3，且滿足斐波那契性質。
- 拆分時，不能有前導零（除非是 0 本身）。
算法設計：
- 使用回溯法枚舉所有可能的拆分方式。
- 對于每個可能的拆分，檢查是否滿足斐波那契性質。
- 如果找到滿足條件的序列，則返回結果。
優化：
- 在回溯過程中，如果當前數字超過 2^31 - 1，則直接剪枝。
- 如果當前數字不滿足斐波那契性質，則剪枝。

3、代碼實現

C++

class Solution {
public:vector<int> splitIntoFibonacci(string num) {vector<int> list;                            // 用于存儲斐波那契序列backtrack(list, num, num.length(), 0, 0, 0); // 調用回調函數return list;                                 // 返回結果}bool backtrack(vector<int>& list, string num, int length, int index, long long sum, int prev) {if (index == length) {return list.size() >= 3; // 如果遍歷完字符串序列且序列長度 >= 3, 返回 true}long long curr = 0; // 當前數字for (int i = index; i < length; ++i) {if (i > index && num[index] == '0') {break; // 如果有前導零, 直接剪枝}curr = curr * 10 + (num[i] - '0'); // 計算當前數字if (curr > INT_MAX) {break; // 如果當前數字超過 2^31 - 1, 剪枝}if (list.size() >= 2) {if (curr < sum) {continue; // 如果當前數字小于 sum, 繼續增加數字} else if (curr > sum) {break; // 如果當前數字大于 sum，剪枝}}list.push_back(curr); // 將當前數字加入序列if (backtrack(list, num, length, i + 1, prev + curr, curr)) {return true;}list.pop_back(); // 回溯, 移除當前數字}return false; // 如果沒有找到滿足條件的序列, 返回 false}
};

Java

class Solution {public List<Integer> splitIntoFibonacci(String num) {List<Integer> list = new ArrayList<>(); // 用于存儲斐波那契序列backtrack(list, num, num.length(), 0, 0, 0); // 調用回溯函數return list; // 返回結果}private boolean backtrack(List<Integer> list, String num, int length, int index, long sum, long prev) {if (index == length) {return list.size() >= 3; // 如果遍歷完字符串且序列長度 >= 3，返回 true}long curr = 0; // 當前數字for (int i = index; i < length; i++) {if (i > index && num.charAt(index) == '0') {break; // 如果有前導零，直接剪枝}curr = curr * 10 + (num.charAt(i) - '0'); // 計算當前數字if (curr > Integer.MAX_VALUE) {break; // 如果當前數字超過 2^31 - 1，剪枝}if (list.size() >= 2) {if (curr < sum) {continue; // 如果當前數字小于 sum，繼續增加數字} else if (curr > sum) {break; // 如果當前數字大于 sum，剪枝}}list.add((int) curr); // 將當前數字加入序列if (backtrack(list, num, length, i + 1, prev + curr, curr)) {return true; // 如果找到滿足條件的序列，返回 true}list.remove(list.size() - 1); // 回溯，移除當前數字}return false; // 如果沒有找到滿足條件的序列，返回 false}
}

Python

class Solution:def splitIntoFibonacci(self, num: str) -> List[int]:def backtrack(index, sum_val, prev, path):if index == len(num):return len(path) >= 3  # 如果遍歷完字符串且序列長度 >= 3，返回 Truecurr = 0  # 當前數字for i in range(index, len(num)):if i > index and num[index] == "0":break  # 如果有前導零，直接剪枝curr = curr * 10 + int(num[i])  # 計算當前數字if curr > 2**31 - 1:break  # 如果當前數字超過 2^31 - 1，剪枝if len(path) >= 2:if curr < sum_val:continue  # 如果當前數字小于 sum，繼續增加數字elif curr > sum_val:break  # 如果當前數字大于 sum，剪枝path.append(curr)  # 將當前數字加入序列if backtrack(i + 1, prev + curr, curr, path):return True  # 如果找到滿足條件的序列，返回 Truepath.pop()  # 回溯，移除當前數字return False  # 如果沒有找到滿足條件的序列，返回 Falseresult = []backtrack(0, 0, 0, result)return result

在這里插入圖片描述

4、復雜度分析

時間復雜度：
- 最壞情況下，回溯的時間復雜度為 O(2ⁿ)，其中 n 是字符串的長度。
- 由于剪枝的存在，實際運行時間會大大減少。
空間復雜度：
- 使用遞歸棧和結果列表，空間復雜度為 O(n)。

Q4、[困難] 猜猜這個單詞

1、題目描述

給你一個由不同字符串組成的單詞列表 words ，其中 words[i] 長度均為 6 。words 中的一個單詞將被選作秘密單詞 secret 。

另給你一個輔助對象 Master ，你可以調用 Master.guess(word) 來猜單詞，其中參數 word 長度為 6 且必須是 words 中的字符串。

Master.guess(word) 將會返回如下結果：

如果 word 不是 words 中的字符串，返回 -1 ，或者
一個整數，表示你所猜測的單詞 word 與 秘密單詞 secret 的準確匹配（值和位置同時匹配）的數目。

每組測試用例都會包含一個參數 allowedGuesses ，其中 allowedGuesses 是你可以調用 Master.guess(word) 的最大次數。

對于每組測試用例，在不超過允許猜測的次數的前提下，你應該調用 Master.guess 來猜出秘密單詞。最終，你將會得到以下結果：

如果你調用 Master.guess 的次數大于 allowedGuesses 所限定的次數或者你沒有用 Master.guess 猜到秘密單詞，則得到 "Either you took too many guesses, or you did not find the secret word." 。
如果你調用 Master.guess 猜到秘密單詞，且調用 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" 是秘密單詞 secret ，共有 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.
解釋：共有 2 個單詞，且其中一個為秘密單詞，可以通過測試用例。

提示：

1 <= words.length <= 100
words[i].length == 6
words[i] 僅由小寫英文字母組成
words 中所有字符串 互不相同
secret 存在于 words 中
10 <= allowedGuesses <= 30

2、解題思路

問題分析：
- 需要從 words 中猜出秘密單詞 secret。
- 每次調用 Master.guess(word) 會返回 word 與 secret 的匹配數目。
- 需要在允許的猜測次數內找到 secret。
算法設計：
- 使用啟發式方法，每次選擇一個單詞進行猜測，并根據返回的匹配數目縮小可能的候選單詞范圍。
- 通過計算單詞之間的匹配數目，選擇能夠最大程度減少候選單詞數量的單詞進行猜測。
優化：
- 使用預計算的匹配矩陣 H，其中 H[i][j] 表示 words[i] 和 words[j] 的匹配數目。
- 在每次猜測后，根據匹配數目過濾候選單詞。

3、代碼實現

C++

class Solution {
private:vector<vector<int>> H; // 匹配矩陣, H[i][j] 表示 words[i] 和 words[j] 的匹配數目// 選擇下一個猜測的單詞int solve(vector<int>& possible, vector<int>& path) {if (possible.size() <= 2) {return possible[0]; // 如果候選單詞數量 <= 2，直接返回第一個}vector<int> ansgrp = possible;int ansguess = -1;// 遍歷所有可能的猜測單詞for (int guess = 0; guess < H.size(); ++guess) {if (find(path.begin(), path.end(), guess) ==path.end()) {                  // 如果 guess 未被猜測過vector<vector<int>> groups(7); // 根據匹配數目分組for (int j : possible) {if (j != guess) {groups[H[guess][j]].push_back(j);}}// 找到最大的組vector<int> maxgroup = groups[0];for (int i = 0; i < 7; ++i) {if (groups[i].size() > maxgroup.size()) {maxgroup = groups[i];}}// 選擇能夠最小化最大組的猜測單詞if (maxgroup.size() < ansgrp.size()) {ansgrp = maxgroup;ansguess = guess;}}}return ansguess;}public:void findSecretWord(vector<string>& words, Master& master) {int N = words.size();H = vector<vector<int>>(N, vector<int>(N, 0)); // 初始化匹配矩陣for (int i = 0; i < N; ++i) {for (int j = i; j < N; ++j) {int match = 0;for (int k = 0; k < 6; ++k) {if (words[i][k] == words[j][k]) {match++;}}H[i][j] = H[j][i] = match; // 計算匹配數目}}vector<int> possible; // 候選單詞列表vector<int> path;     // 已猜測的單詞列表for (int i = 0; i < N; ++i) {possible.push_back(i);}while (!possible.empty()) {int guess = solve(possible, path);        // 選擇下一個猜測單詞int matches = master.guess(words[guess]); // 調用 Master.guessif (matches == words[0].length()) {return; // 如果猜中，直接返回}vector<int> possible2; // 新的候選單詞列表for (int j : possible) {if (H[guess][j] == matches) {possible2.push_back(j); // 根據匹配數目過濾候選單詞}}possible = possible2;path.push_back(guess); // 將猜測單詞加入已猜測列表}}
};

Java

class Solution {private int[][] H; // 匹配矩陣，H[i][j] 表示 words[i] 和 words[j] 的匹配數目// 選擇下一個猜測的單詞private int solve(List<Integer> possible, List<Integer> path) {if (possible.size() <= 2) {return possible.get(0); // 如果候選單詞數量 <= 2，直接返回第一個}List<Integer> ansgrp = possible;int ansguess = -1;// 遍歷所有可能的猜測單詞for (int guess = 0; guess < H.length; guess++) {if (!path.contains(guess)) { // 如果 guess 未被猜測過List<List<Integer>> groups = new ArrayList<>(7);for (int i = 0; i < 7; i++) {groups.add(new ArrayList<>());}for (int j : possible) {if (j != guess) {groups.get(H[guess][j]).add(j); // 根據匹配數目分組}}// 找到最大的組List<Integer> maxgroup = groups.get(0);for (int i = 0; i < 7; i++) {if (groups.get(i).size() > maxgroup.size()) {maxgroup = groups.get(i);}}// 選擇能夠最小化最大組的猜測單詞if (maxgroup.size() < ansgrp.size()) {ansgrp = maxgroup;ansguess = guess;}}}return ansguess;}public void findSecretWord(String[] words, Master master) {int N = words.length;H = new int[N][N]; // 初始化匹配矩陣for (int i = 0; i < N; i++) {for (int j = i; j < N; j++) {int match = 0;for (int k = 0; k < 6; k++) {if (words[i].charAt(k) == words[j].charAt(k)) {match++;}}H[i][j] = H[j][i] = match; // 計算匹配數目}}List<Integer> possible = new ArrayList<>(); // 候選單詞列表List<Integer> path = new ArrayList<>(); // 已猜測的單詞列表for (int i = 0; i < N; i++) {possible.add(i);}while (!possible.isEmpty()) {int guess = solve(possible, path); // 選擇下一個猜測單詞int matches = master.guess(words[guess]); // 調用 Master.guessif (matches == words[0].length()) {return; // 如果猜中，直接返回}List<Integer> possible2 = new ArrayList<>(); // 新的候選單詞列表for (int j : possible) {if (H[guess][j] == matches) {possible2.add(j); // 根據匹配數目過濾候選單詞}}possible = possible2;path.add(guess); // 將猜測單詞加入已猜測列表}}
}

Python

class Solution:def __init__(self):self.H = []  # 匹配矩陣，H[i][j] 表示 words[i] 和 words[j] 的匹配數目# 選擇下一個猜測的單詞def solve(self, possible: List[int], path: List[int]) -> int:if len(possible) <= 2:return possible[0]  # 如果候選單詞數量 <= 2，直接返回第一個ansgrp = possibleansguess = -1# 遍歷所有可能的猜測單詞for guess in range(len(self.H)):if guess not in path:  # 如果 guess 未被猜測過groups = [[] for _ in range(7)]  # 根據匹配數目分組for j in possible:if j != guess:groups[self.H[guess][j]].append(j)# 找到最大的組maxgroup = groups[0]for i in range(7):if len(groups[i]) > len(maxgroup):maxgroup = groups[i]# 選擇能夠最小化最大組的猜測單詞if len(maxgroup) < len(ansgrp):ansgrp = maxgroupansguess = guessreturn ansguessdef findSecretWord(self, words: List[str], master: "Master") -> None:N = len(words)self.H = [[0] * N for _ in range(N)]  # 初始化匹配矩陣for i in range(N):for j in range(i, N):match = 0for k in range(6):if words[i][k] == words[j][k]:match += 1self.H[i][j] = self.H[j][i] = match  # 計算匹配數目possible = list(range(N))  # 候選單詞列表path = []  # 已猜測的單詞列表while possible:guess = self.solve(possible, path)  # 選擇下一個猜測單詞matches = master.guess(words[guess])  # 調用 Master.guessif matches == len(words[0]):return  # 如果猜中，直接返回possible = [j for j in possible if self.H[guess][j] == matches]  # 根據匹配數目過濾候選單詞path.append(guess)  # 將猜測單詞加入已猜測列表