Google Coding Interview Question | Leetcode 211 | Design Add and Search Words Data Structure

In this video, we introduce how to solve the "Design Add and Search Words Data Structure" question which is used by big tech companies like Google, Facebook, Amazon in coding interviews. We also cover how to behave during a coding interview, e.g. communication, testing, coding style, etc.

Please subscribe to this channel if you like this video. I will keep updating this channel with videos covering different topics in interviews from big tech companies.

[angelsancheese]

# Python version of your code exceeded memory limit. Using a list for self.children..
class Node:
def __init__(self, is_word=False):
self.is_word = is_word
self.children = [None for _ in range(26)]

class WordDictionary:

def __init__(self):
self.root = Node()

def addWord(self, word: str) -> None:
current_node = self.root
i = 0
while i < len(word):
c = word[i]
c_index = ord(c) - 97
if != None:
current_node =
else:
new_node = Node(is_word=False)
= new_node
current_node = new_node
i = i + i
current_node.is_word = True

def searchHelper(self, word, index, current_node):
if index == len(word) - 1:
return current_node.is_word
c = word[index]
c_index = ord(c) - 97
if c != '.':
if == None:
return False
return self.searchHelper(word, index+1,
for c_index in current_node.children:
if c_index == None:
continue
if self.searchHelper(word, index+1,
return True
return False

def search(self, word: str) -> bool:
return self.searchHelper(word, 0, self.root)

[angelsancheese]

# Python version of your code exceeded the memory limit. What is a better solution? use list [] for self.children?
class Node:
def __init__(self, is_word=False):
self.is_word = is_word
self.children = {}

class WordDictionary:

def __init__(self):
self.root = Node()

def addWord(self, word: str) -> None:
current_node = self.root
i = 0
while i < len(word):
if word[i] in
current_node =
else:
new_node = Node(is_word=False)
= new_node
current_node = new_node
i = i + i
current_node.is_word = True

def searchHelper(self, word, index, current_node):
if index == len(word) - 1:
return current_node.is_word
c = word[index]
if c != '.':
if c not in
return False
return self.searchHelper(word, index+1,
for key in
if self.searchHelper(word, index+1,
return True
return False

def search(self, word: str) -> bool:
return self.searchHelper(word, 0, self.root)