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%）

1. 建立一個 collections class 中的 defaultdict() ，命名為 word_store

2. [addWord] --> 依據字串長度來分 list 存： [ ( 2, ["ab", "dv"] ), ( 1, ["a","b","c"] ), ( 6, [ "asdfgh"] ) ]

3. [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