计算word之间的匹配度,
每次猜完把不符合匹配度的删去,得到一个可行的list
在list中启发式选择j
这里用的启发方法是,计算每一个word,求出匹配度0-6之间最高的匹配数,我选择这样的值最小的word,希望这样能够让搜索空间尽量变小
C++ 代码
/**
* // This is the Master's API interface.
* // You should not implement it, or speculate about its implementation
* class Master {
* public:
* int guess(string word);
* };
*/
class Solution {
public:
vector<bool> st;
vector<vector<int>> f;
int n;
int get(int j , int u){
int res= 0;
for (int i = 0;i<n;i++){
if (f[i][j] == u) res++;
}
return res;
}
void findSecretWord(vector<string>& wordlist, Master& master) {
n = wordlist.size();
st = vector<bool>(n,0);
f = vector<vector<int>>(n, vector<int>(n,0));
// cout<<1;
for (int i = 0;i<n;i++){
for (int j = 0;j<n;j++){
int sum = 0;
for (int k =0;k<6;k++){
if (wordlist[i][k] == wordlist[j][k]) sum++;
}
f[i][j] = sum;
}
}
// cout<<1;
for (int i = 0;i<10;i++){
// if (st[i]) continue;
int k = -1, m = INT_MAX;//find smallest
for (int j = 0;j<n;j++){
if (st[j]) continue;
int t= 0;
for (int u = 0;u<=6;u++){
t = max(t, get(j,u));
}
if (t<m) {m = t; k = j;}
}
int match = master.guess(wordlist[k]);
if (match == 6) break;
st[k] = 1;
for (int j=0;j<n;j++) if (f[k][j] != match) st[j] = 1;
}
}
};