Tries

Question 1

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Answer 1

• Implement a TrieNode class and a Trie class, no search function required but REMOVE function needed. Review the TrieNode.refs attribute to simply removal.
• Do backtracking DFS on the grid, tracking (row, col), curNode, and curWord.

class TrieNode:
def __init__(self):
self.children = {}
self.isWord = False
self.refs = 0

def addWord(self, word):
    cur = self
    cur.refs += 1
    for c in word:
        if c not in cur.children:
            cur.children[c] = TrieNode()
        cur = cur.children[c]
        cur.refs += 1
    cur.isWord = True

def removeWord(self, word):
    cur = self
    cur.refs -= 1
    for c in word:
        if c in cur.children:
            cur = cur.children[c]
            cur.refs -= 1

class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = TrieNode()
for w in words:
root.addWord(w)

    ROWS, COLS = len(board), len(board[0])
    res, visit = set(), set()

    def dfs(r, c, node, word):
        if (
            r not in range(ROWS) 
            or c not in range(COLS)
            or board[r][c] not in node.children
            or node.children[board[r][c]].refs < 1
            or (r, c) in visit
        ):
            return

        visit.add((r, c))
        node = node.children[board[r][c]]
        word += board[r][c]
        if node.isWord:
            node.isWord = False
            res.add(word)
            root.removeWord(word)

        dfs(r + 1, c, node, word)
        dfs(r - 1, c, node, word)
        dfs(r, c + 1, node, word)
        dfs(r, c - 1, node, word)
        visit.remove((r, c))

    for r in range(ROWS):
        for c in range(COLS):
            dfs(r, c, root, "")

    return list(res)

Question 2

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Answer 2

class TrieNode:
def __init__(self):
self.children = {} # of char to TrieNode
self.endOfWord = False

class Trie:
def __init__(self):
self.root = TrieNode()

def insert(self, word: str) -> None:
    current = self.root
    for char in word:
        if not char in current.children:
            current.children[char] = TrieNode()
        current = current.children[char]
    current.endOfWord = True

def search(self, word: str) -> bool:
    current = self.root
    for char in word:
        if not char in current.children:
            return False
        current = current.children[char]
    return current.endOfWord

def startsWith(self, prefix: str) -> bool:
    current = self.root
    for char in prefix:
        if not char in current.children:
            return False
        current = current.children[char]
    return True

Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

Question 3

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots ‘.’ where dots can be matched with any letter.

Answer 3

class TrieNode:
def __init__(self):
self.children = {}
self.endOfWord = False

class WordDictionary:

def \_\_init\_\_(self):
    self.root = TrieNode()

def addWord(self, word: str) -> None:
    cur = self.root
    for c in word:
        if not c in cur.children:
            cur.children[c] = TrieNode()
        cur = cur.children[c]
    cur.endOfWord = True

def search(self, word: str) -> bool:
    def searchRecur(root, word):
        cur = root
        for i in range(len(word)):
            c = word[i]
            if c == '.':
                for child in cur.children.values():
                    if searchRecur(child, word[i + 1:]):
                        return True
                return False
            elif not c in cur.children:
                return False
            cur = cur.children[c]
        return cur.endOfWord
    return searchRecur(self.root, word)

. can be any character, so look at every child of current node
# see if any of them contain the next letter
# do a recursive call of the function on the remaining portion of the word with
# current as new root

Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)