211. Add and Search Word - Data structure design
Question 211
https://leetcode.com/problems/add-and-search-word-data-structure-design
Design a data structure that supports the following two operations:
void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z
or .
. A .
means it can represent any one letter.
Example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z
.
Answer
v1.use defaultdict (98.83%)
建立一個 collections class 中的 defaultdict() ,命名為 word_store
[addWord] --> 依據字串長度來分 list 存: [ ( 2, ["ab", "dv"] ), ( 1, ["a","b","c"] ), ( 6, [ "asdfgh"] ) ]
[search] -->
a) 如果該 search 字串沒有 “.” ,直接找 word_store 中該長度的字串有沒有符合的 b) 如果有 “.”,一個字母一個字母去比對該長度 list 中的字詞
class WordDictionary(object):
def __init__(self):
# Initialize a collection to store words
self.word_store = collections.defaultdict(list)
def addWord(self, word):
# Adds a word into word_store
# Classified by how long is the word
self.word_store[len(word)].append(word)
def search(self, word):
word_len = len(word)
if '.' not in word:
return word in self.word_store[len(word)]
else:
for item in self.word_store[word_len]:
# Comparison character one by one
for alpha in range(0,word_len):
if word[alpha] != "." and word[alpha] != item[alpha]:
break
if alpha == (word_len-1) :
return True
return False
Last updated