骨骼清奇Word Games

Catalog:
LC 890 Find and Replace Pattern
LC 843 Guess the Word
LC 299 Bulls and Cows
LC 676 Implement Magic Dictionary

LC八就灵及其变种（找word pattern）
频率：8
Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
1 <= words.length <= 50
1 <= pattern.length = words[i].length <= 20

分析：如何找到一个word的base pattern?每个字母又它在单词里第一次出现的位置作为id。

'aba' -> [0,1,0]
'abb' -> [0,1,1]

#beat 99%
class Solution:
    def findAndReplacePattern(self, words, pattern):
        """
        :type words: List[str]
        :type pattern: str
        :rtype: List[str]
        """
        def BaseP(w):
            m = {}
            for c in w: m[c] = m.get(c, len(m))
            return "".join(chr(m[c] + 97) for c in w)
        p = BaseP(pattern)
        res = []
        for w in words:
            if len(w) == len(p) and BaseP(w) == p:
                res.append(w)
        return res

LC 843 Guess the Word [Freq: 9]
We need to call master.guess() less than 10 times to find out what is the secret word in the word list given.
Example 1:
Input: secret = "acckzz", wordlist = ["acckzz","ccbazz","eiowzz","abcczz"]
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.

Solution: repeatedly choose a word to guess and eliminate all words that do not have the same number of matches as the chosen word. This is O(n) time and not O(n^2) because I don't check all pairs.

LC 299 Bulls and Cows
Input: secret = "1123", guess = "0111"
Output: "1A1B"
Explanation: The 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow.
Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows").

Key: dict a "&" dict b operation will keep pars in a, the key of which appears in b.

    s, g = Counter(secret), Counter(guess)
    a = sum(i == j for i, j in zip(secret, guess))
    return '%sA%sB' % (a, sum((s & g).values()) - a)

LC 676 Implement Magic Dictionary
For the method buildDict, you'll be given a list of non-repetitive words to build a dictionary.
For the method search, you'll be given a word, and judge whether if you modify exactly one character into another character in this word, the modified word is in the dictionary you just built.

Input: buildDict(["hello", "leetcode"]), Output: Null
Input: search("hello"), Output: False
Input: search("hhllo"), Output: True
Input: search("hell"), Output: False
Input: search("leetcoded"), Output: False

Approach #1: Brute Force with Bucket-By-Length

class MagicDictionary(object):
    def __init__(self):
        self.buckets = collections.defaultdict(list)

    def buildDict(self, words):
        for word in words:
            self.buckets[len(word)].append(word)

    def search(self, word):
        return any(sum(a!=b for a,b in zip(word, candidate)) == 1
                   for candidate in self.buckets[len(word)])

Approach #2: Generalized Neighbors

class MagicDictionary(object):
    def _genneighbors(self, word):
        for i in xrange(len(word)):
            yield word[:i] + '*' + word[i+1:]

    def buildDict(self, words):
        self.words = set(words)
        self.count = collections.Counter(nei for word in words
                                        for nei in self._genneighbors(word))

    def search(self, word):
        return any(self.count[nei] > 1 or
                   self.count[nei] == 1 and word not in self.words
                   for nei in self._genneighbors(word))

class MagicDictionary():

    def __init__(self):
        self.trie = {}

    def buildDict(self, d):
        for word in d: 
            node = self.trie 
            for letter in word: 
                if letter not in node: 
                    node[letter] = {}
                node = node[letter] 
            node[None] = None