Skip to content

Trie (Keyword Tree)

Introduction

Explore - LeetCode

Trie (Keyword Tree) Tutorials & Notes | Data Structures | HackerEarth

Article on Trie. General Template and List of problems. - LeetCode Discuss

Simple Trie

Screenshot 2021-08-31 at 09.42.21.png

class Trie:
    def __init__(self):
        self.root = {}
        self.endSymbol = endSymbol

    def add(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                current[letter] = {}
            current = current[letter]
        current[self.endSymbol] = word

    def remove(self, word):
        self.delete(self.root, word, 0)

    def delete(self, dicts, word, i):
        if i == len(word):
            if '*' in dicts:
                del dicts['*']
                if len(dicts) == 0:
                    return True
                else:
                    return False
            else:
                return False
        else:
            if word[i] in dicts and self.delete(dicts[word[i]], word, i + 1):
                if len(dicts[word[i]]) == 0:
                    del dicts[word[i]]
                    return True
                else:
                    return False

            else:
                return False

Examples

  • Design Add and Search Words Data Structure

    """ 
    211. Design Add and Search Words Data Structure:
    
    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.
    
    
    Example:
        Input
            ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
            [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
        Output
            [null,null,null,null,false,true,true,true]
        Explanation
            WordDictionary wordDictionary = new WordDictionary();
            wordDictionary.addWord("bad");
            wordDictionary.addWord("dad");
            wordDictionary.addWord("mad");
            wordDictionary.search("pad"); // return False
            wordDictionary.search("bad"); // return True
            wordDictionary.search(".ad"); // return True
            wordDictionary.search("b.."); // return True
    
    https://leetcode.com/problems/design-add-and-search-words-data-structure
    """
    
    class WordDictionary:
    
        def __init__(self):
            self.root = {}
            self.end_symbol = "*"
    
        def addWord(self, word: str):
            curr_root = self.root
            for char in word:
                if char not in curr_root:
                    curr_root[char] = {}
                curr_root = curr_root[char]
            curr_root[self.end_symbol] = True
    
        def search(self, word: str):
            return self.search_helper(word, 0, self.root)
    
        def search_helper(self, word, idx, curr_root):
            # end of word
            if idx == len(word):
                return self.end_symbol in curr_root
            # no matching char
            if word[idx] != "." and word[idx] not in curr_root:
                return False
    
            if word[idx] == ".":
                for letter in curr_root:
                    if letter != self.end_symbol and self.search_helper(word, idx+1, curr_root[letter]):
                        return True
                return False
            else:
                return self.search_helper(word, idx+1, curr_root[word[idx]])
    
    # Your WordDictionary object will be instantiated and called as such:
    # obj = WordDictionary()
    # obj.addWord(word)
    # param_2 = obj.search(word)
    
  • Boggle Board/Word Search II

    """ 
    Word Search II
    
    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.
    https://leetcode.com/problems/word-search-ii/
    """
    
    """
    Boggle Board:
    You're given a two-dimensional array (a matrix) of potentially unequal height and width containing letters;
     this matrix represents a boggle board. You're also given a list of words.
    Write a function that returns an array of all the words contained in the boggle board. The final words don't need to be in any particular order.
    A word is constructed in the boggle board by connecting adjacent (horizontally, vertically, or diagonally) letters,
     without using any single letter at a given position more than once; while a word can of course have repeated letters,
     those repeated letters must come from different positions in the boggle board in order for the word to be contained in the board.
    Note that two or more words are allowed to overlap and use the same letters in the boggle board.
    
    Sample Input
        board = [
        ["t", "h", "i", "s", "i", "s", "a"],
        ["s", "i", "m", "p", "l", "e", "x"],
        ["b", "x", "x", "x", "x", "e", "b"],
        ["x", "o", "g", "g", "l", "x", "o"],
        ["x", "x", "x", "D", "T", "r", "a"],
        ["R", "E", "P", "E", "A", "d", "x"],
        ["x", "x", "x", "x", "x", "x", "x"],
        ["N", "O", "T", "R", "E", "-", "P"],
        ["x", "x", "D", "E", "T", "A", "E"],
        ],
        words = [
        "this", "is", "not", "a", "simple", "boggle",
        "board", "test", "REPEATED", "NOTRE-PEATED",
        ]
    Sample Output
        ["this", "is", "a", "simple", "boggle", "board", "NOTRE-PEATED"]
        // The words could be ordered differently.
    
    https://www.algoexpert.io/questions/Boggle%20Board
    """
    
    """ 
    ------------------------------------------------------------------------------------------------------------------------------
    """
    
    def boggleBoardBF(board, words):
        found_words = []
    
        for row in range(len(board)):
            for col in range(len(board[row])):
    
                # look for each word
                for idx in range(len(words)):
                    if words[idx] != '-1':
                        if find_word(board, words, found_words, idx, 0, row, col):
                            found_words.append(words[idx])
                            # mark word as visted
                            words[idx] = '-1'
    
        return found_words
    
    def find_word(board, words, found_words, curr_word_idx,  curr_char_idx, row, col):
        # had found word
        if words[curr_word_idx] == '-1':
            return False
    
        word = words[curr_word_idx]
    
        # found word
        if curr_char_idx >= len(word):
            return True
    
        # out of bounds
        if row < 0 or col < 0 or row >= len(board) or col >= len(board[0]):
            return False
    
        # was visited
        if board[row][col] == '000':
            return False
    
        curr_char = board[row][col]
    
        # cannot make word
        if curr_char != word[curr_char_idx]:
            return False
    
        # mark as visited
        board[row][col] = '000'
    
        # explore
        top = find_word(board, words, found_words, curr_word_idx,
                        curr_char_idx+1, row+1, col)
        bottom = find_word(board, words, found_words, curr_word_idx,
                           curr_char_idx+1, row-1, col)
        left = find_word(board, words, found_words, curr_word_idx,
                         curr_char_idx+1, row, col-1)
        right = find_word(board, words, found_words, curr_word_idx,
                          curr_char_idx+1, row, col+1)
        top_left = find_word(board, words, found_words, curr_word_idx,
                             curr_char_idx+1, row+1, col-1)
        top_right = find_word(board, words, found_words, curr_word_idx,
                              curr_char_idx+1, row+1, col+1)
        bottom_left = find_word(board, words, found_words, curr_word_idx,
                                curr_char_idx+1, row-1, col-1)
        bottom_right = find_word(board, words, found_words, curr_word_idx,
                                 curr_char_idx+1, row-1, col+1)
    
        # unmark
        board[row][col] = curr_char
    
        return top or bottom or left or right or top_left or top_right or bottom_left or bottom_right
    
    """ 
    ------------------------------------------------------------------------------------------------------------------------------
    
    use a Trie
    """
    
    """ 
    ------------------------------------------------------------------------------------------------------------------------------
    
    use a Trie
    """
    
    endSymbol = "*"
    
    class Trie:
        def __init__(self):
            self.root = {}
            self.endSymbol = endSymbol
    
        def add(self, word):
            current = self.root
            for letter in word:
                if letter not in current:
                    current[letter] = {}
                current = current[letter]
            current[self.endSymbol] = word
    
        def remove(self, word):
            self.delete(self.root, word, 0)
    
        def delete(self, dicts, word, i):
            if i == len(word):
                if '*' in dicts:
                    del dicts['*']
                    if len(dicts) == 0:
                        return True
                    else:
                        return False
                else:
                    return False
            else:
                if word[i] in dicts and self.delete(dicts[word[i]], word, i + 1):
                    if len(dicts[word[i]]) == 0:
                        del dicts[word[i]]
                        return True
                    else:
                        return False
    
                else:
                    return False
    
    class Solution:
        def findWords(self, board, words):
            trie = Trie()
            for word in words:
                trie.add(word)
    
            found_words = {}
    
            for row in range(len(board)):
                for col in range(len(board[row])):
                    self.explore(trie, row, col, trie.root, board, found_words)
    
            return list(found_words.keys())
    
        def get_neighbours(self, i, j, board):
            neighbours = []
            if i > 0:
                neighbours.append([i - 1, j])
            if i < len(board) - 1:
                neighbours.append([i + 1, j])
            if j > 0:
                neighbours.append([i, j - 1])
            if j < len(board[0]) - 1:
                neighbours.append([i, j + 1])
            return neighbours
    
        def explore(self, main_trie, row, col, trie, board, found_words):
            mark = -1
    
            # # validate
            if board[row][col] not in trie:
                return
            if board[row][col] == mark:
                return
    
            char = board[row][col]
            curr_trie = trie[char]
    
            # # record all words found
            if endSymbol in curr_trie:
                word = curr_trie[endSymbol]
                found_words[word] = True
                main_trie.remove(word)
    
            # # continue search
            board[row][col] = mark  # visit - mark visited
            for neighbour in self.get_neighbours(row, col, board):
                self.explore(
                    main_trie, neighbour[0], neighbour[1], curr_trie, board, found_words)
            board[row][col] = char  # univisit - remove mark
    
    """ 
    ---------------------------------------------------------
    """
    
    def get_neighbours(i, j, board):
    
        neighbours = []
    
        if i > 0 and j > 0:
            neighbours.append([i - 1, j - 1])
        if i > 0 and j < len(board[0]) - 1:
            neighbours.append([i - 1, j + 1])
        if i < len(board) - 1 and j < len(board[0]) - 1:
            neighbours.append([i + 1, j + 1])
        if i < len(board) - 1 and j > 0:
            neighbours.append([i + 1, j - 1])
        if i > 0:
            neighbours.append([i - 1, j])
        if i < len(board) - 1:
            neighbours.append([i + 1, j])
        if j > 0:
            neighbours.append([i, j - 1])
        if j < len(board[0]) - 1:
            neighbours.append([i, j + 1])
        return neighbours
    
    def explore(row, col, trie, board, found_words):
        mark = -1
    
        # # validate
        if board[row][col] not in trie:
            return
        if board[row][col] == mark:
            return
    
        char = board[row][col]
        curr_trie = trie[char]
    
        # # record all words found
        if "*" in curr_trie:
            found_words[curr_trie["*"]] = True
    
        # # continue search
        board[row][col] = mark  # visit - mark visited
        for neighbour in get_neighbours(row, col, board):
            explore(neighbour[0], neighbour[1], curr_trie, board, found_words)
        board[row][col] = char  # univisit - remove mark
    
    def boggleBoard(board, words):
        trie = Trie()
        for word in words:
            trie.add(word)
    
        found_words = {}
    
        for row in range(len(board)):
            for col in range(len(board[row])):
                explore(row, col, trie.root, board, found_words)
    
        return list(found_words.keys())
    
    """ 
    ------------------------------------------------------------------------------------------------------------------------------
    """
    


Find the original version of this page (with additional content) on Notion here.



Last update: November 20, 2021 07:19:02
Created: November 20, 2021 07:19:02
Authors: paulonteri (98.75%), Not Committed Yet (1.25%)