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
