LeetCode 843 Guess the Word

LeetCode

This is an interactive problem.

You are given an array of unique strings wordlist where wordlist[i] is 6 letters long, and one word in this list is chosen as secret.

You may call Master.guess(word) to guess a word. The guessed word should have type string and must be from the original list with 6 lowercase letters.

This function returns an integer type, representing the number of exact matches (value and position) of your guess to the secret word. Also, if your guess is not in the given wordlist, it will return -1 instead.

For each test case, you have exactly 10 guesses to guess the word. At the end of any number of calls, if you have made 10 or fewer calls to Master.guess and at least one of these guesses was secret, then you pass the test case.

Example 1:

Input: secret = “acckzz”, wordlist = [“acckzz”,”ccbazz”,”eiowzz”,”abcczz”], numguesses = 10
Output: You guessed the secret word correctly.
Explanation:
master.guess(“aaaaaa”) returns -1, because “aaaaaa” is not in wordlist.
master.guess(“acckzz”) returns 6, because “acckzz” is secret and has all 6 matches.
master.guess(“ccbazz”) returns 3, because “ccbazz” has 3 matches.
master.guess(“eiowzz”) returns 2, because “eiowzz” has 2 matches.
master.guess(“abcczz”) returns 4, because “abcczz” has 4 matches.
We made 5 calls to master.guess and one of them was the secret, so we pass the test case.

Example 2:

Input: secret = “hamada”, wordlist = [“hamada”,”khaled”], numguesses = 10
Output: You guessed the secret word correctly.

Constraints:

1 <= wordlist.length <= 100 wordlist[i].length == 6
wordlist[i] consist of lowercase English letters. All the strings of wordlist are unique.
secret exists in wordlist. numguesses == 10

题目大意：

给定单词列表，每个单词长度为6， 其中一个为答案，每次猜一个单词。给一个API会告诉你猜的单词有多少位命中(位置,数值), 求是否可以10次内猜对

暴力法解题思路：

较直观的解法是抽第一个单词出来，然后call API, 然后再filter wordlist使得新的单词列表里的单词的命中位数也是一样的。每轮缩少范围。

解题步骤：

N/A

注意事项：

1. Python代码：

   def findSecretWord2(self, wordlist, master):
   	for i in range(10):
   		guess = wordlist[0]
   		res = master.guess(guess)
   		wordlist = [w for w in wordlist if self.match(w, guess) == res]
   
   def match(self, w1, w2):
   	return sum(i == j for i, j in zip(w1, w2))

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

---

统计频率算法II解题思路(推荐)：

上述方法跟单词个数有关，如果很多的话，就会超过10次。考虑单词长度为6，而可以猜10次。考虑用26字母存储法，也就是统计频率。统计每位的频率，然后将频率作为这一位的分数，求每个单词的总分。
一定要选择单词列表中的某个单词去猜，如果不在列表中返回为-1，这个信息没有任何作用。
选择总分最高的去猜，原理是它最具代表性，这样可以快速排除很多单词，有点类似于二分法。反之，若用频率低的单词，也就只能排除一个单词。

Python代码：

def findSecretWord(self, wordlist, master):
	for _ in range(10):
		char_to_count = [collections.Counter(w[i] for w in wordlist) for i in range(6)]
		guess = max(wordlist, key=lambda w: sum(char_to_count[i][char] for i, char in enumerate(w)))
		res = master.guess(guess)
		wordlist = [w for w in wordlist if self.match(w, guess) == res]

def match(self, w1, w2):
	return sum(i == j for i, j in zip(w1, w2))

算法分析：

时间复杂度为O(n)，空间复杂度O(1)