interactive
string
]
Leetcode 0843 Guess the Word
Problem statement
https://leetcode.com/problems/guess-the-word/
Solution 1
Quite difficult for me problem, mainly because of new interactive concept. Note, that there is always will be small probability, that solution will not be accepted, and I do not like it.
So, what is the main idea here? We have a list of words, and we need to find the secret word among these words. Let us try the following strategy: choose some of this words (how exactly, a bit later), apply master.guess()
function to this word, imagine we have result t
. Now, for every other word, we compare how many matches we have with given word, and if number if not t
, we can for sure eliminate this word. We continue this process, until we have only one word left or we found word with 6
matches.
So, now the question, how to choose the word we want to test?
- We can just choose first word (or last, or random) and if we are lucky testing system will admit this solution, I tried it and it is working sometimes.
- Choose the word, such that if we delete it, we can eliminate the biggest number of words. Note first of all, that there is $(25/26)^6 \approx 0.8$ probability that two words will not have any matches at all, because it is given that letters chosen uniformly independent. So, let us for each word find number of words such that number of matches is equal to $0$ and chose
mininmum
of them. Why minimum and not maximum? Imagine we found word, which has0
matches with any other word, then if it happen thatmaster.guess()
is equal to0
(and it happen with probability0.8
), then we will not eliminate anything at all.
Complexity
Time complexity is O(n^2*log n)
in average, because on each iteration we spend O(n^2)
time and potentially we have O(log n)
iterations.
Code
class Solution:
def findSecretWord(self, wordlist, master: 'Master'):
def match(w1, w2): return sum(i==j for i,j in zip(w1, w2))
while wordlist:
count = Counter(w1 for w1, w2 in permutations(wordlist, 2) if match(w1, w2) == 0)
guess = min(wordlist, key=lambda w: count[w])
t = master.guess(guess)
if t == 6: return
wordlist = [w for w in wordlist if match(w, guess) == t]
Solution 2
We also can use another heuristic to choose the best word: for each of 6
places and 26
letters we first count how many words have them. Then we choose the word, which highest score: the word, which in some sense most similar to all others.
Complexity
Time complexity will be O(n log n)
.
Code
class Solution:
def findSecretWord(self, wordlist, master: 'Master'):
def match(w1, w2): return sum(i==j for i,j in zip(w1, w2))
while wordlist:
count = [Counter(w[i] for w in wordlist) for i in range(6)]
guess = max(wordlist, key=lambda w: sum(count[i][c] for i, c in enumerate(w)))
t = master.guess(guess)
if t == 6: return
wordlist = [w for w in wordlist if match(w, guess) == t]