843. Guess the Word - cocoder39/coco39_LC GitHub Wiki

843. Guess the Word

Problem breakdown

• Step 1: find a candidate word to guess
• Step 2: guess the word and then use the match count to narrow down search space

best candidate deep dive

• Option 1: select first element in candidate list
• Option 2: randomly select an element from candidate list
• Option 3: heuristic
  • least 0: To reduce the chance of selecting a word that has too many 0 match with other words, we heuristically select a word that can minimize the number of 0 match with other words
  • max overlap: matchScorep[i][j]: number of words of which the value at index i is ord('a') + j

class Solution:
    def findSecretWord(self, wordlist: List[str], master: 'Master') -> None:
        def countMatch(word1, word2):
            cnt = 0
            for ch1, ch2 in zip(word1, word2):
                if ch1 == ch2:
                    cnt += 1
            return cnt
        
        def getOverlapScore(word):
            score = 0
            for i, ch in enumerate(word):
                idx = ord(ch) - ord('a')
                score += matchScore[i][idx]
            return score
        
        matchScore = [[0] * 26 for i in range(6)]
        for word in wordlist:
            for i, ch in enumerate(word):
                idx = ord(ch) - ord('a')
                matchScore[i][idx] += 1
        
        n = len(wordlist)
        matchCount = [[-1] * n for i in range(n)]
        for i in range(n):
            for j in range(i):
                cnt = countMatch(wordlist[i], wordlist[j])
                matchCount[i][j] = cnt
                matchCount[j][i] = cnt
                
        candidates = wordlist[:]
        candidateMap = {word: i for i, word in enumerate(wordlist)}
        for i in range(10):
            candidates.sort(key=lambda c: getOverlapScore(c), reverse=True)
            cur = candidates[0]
            curIdx = candidateMap.get(cur)
            match = master.guess(cur)
            if match == 6:
                break
            
            temp = []
            for j in range(n):
                if matchCount[curIdx][j] == match:
                    temp.append(wordlist[j])
            candidates = list(set(temp) & set(candidates))