Tries

本記事は以下記事の一部です。

NeetCode 150 全問の解き方とポイントまとめ & 感想

TrieはTreesの発展でたった3問しかないですが、NeetCodeのRoad Mapでも独立している感じで、HeapやBacktrackingとまとめるのも変なので独立した記事にします。

61. Implement Trie Prefix Tree

Problem

A prefix tree (also known as a trie) is a tree data structure used to efficiently store and retrieve keys in a set of strings. Some applications of this data structure include auto-complete and spell checker systems.

Implement the PrefixTree class:

• PrefixTree() Initializes the prefix tree object.
• void insert(String word) Inserts the string word into the prefix tree.
• boolean search(String word) Returns true if the string word is in the prefix tree (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.

Example 1:

Input: 
["Trie", "insert", "dog", "search", "dog", "search", "do", "startsWith", "do", "insert", "do", "search", "do"]

Output:
[null, null, true, false, true, null, true]

Explanation:
PrefixTree prefixTree = new PrefixTree();
prefixTree.insert("dog");
prefixTree.search("dog");    // return true
prefixTree.search("do");     // return false
prefixTree.startsWith("do"); // return true
prefixTree.insert("do");
prefixTree.search("do");     // return true

Copy

Constraints:

• 1 <= word.length, prefix.length <= 1000
• word and prefix are made up of lowercase English letters.

Solution

class TrieNode:
    def __init__(self):
        self.children = {} # alphabet -> TrieNode
        self.endOfWord = False

class PrefixTree:

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

    def insert(self, word: str) -> None:
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.endOfWord = True
    
    def search(self, word: str) -> bool:
        curr = self.root
        for c in word:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        return curr.endOfWord

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

62. Design Add And Search Words Data Structure

Problem

Design a data structure that supports adding new words and searching for existing words.

Implement the WordDictionary class:

• void addWord(word) Adds word to the data structure.
• 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 1:

Input:
["WordDictionary", "addWord", "day", "addWord", "bay", "addWord", "may", "search", "say", "search", "day", "search", ".ay", "search", "b.."]

Output:
[null, null, null, null, false, true, true, true]

Explanation:
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("day");
wordDictionary.addWord("bay");
wordDictionary.addWord("may");
wordDictionary.search("say"); // return false
wordDictionary.search("day"); // return true
wordDictionary.search(".ay"); // return true
wordDictionary.search("b.."); // return true

Copy

Constraints:

• 1 <= word.length <= 20
• word in addWord consists of lowercase English letters.
• word in search consist of '.' or lowercase English letters.

Solution

class TrieNode:
    def __init__(self):
        self.children = {} # alphabet -> TrieNode
        self.endOfWord = False

class WordDictionary:

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

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

    def search(self, word: str) -> bool:
        
        def dfs(i: int, node: TrieNode) -> bool:
            curr = node
            for j in range(i, len(word)):
                c = word[j]
                if c == '.':
                    for child in curr.children.values():
                        if dfs(j+1, child):
                            return True
                    return False
                else:
                    if c not in curr.children:
                        return False
                    curr = curr.children[c]
            return curr.endOfWord
        
        return dfs(0, self.root)

63. Word Search II

Problem

Given a 2-D grid of characters board and a list of strings words, return all words that are present in the grid.

For a word to be present it must be possible to form the word with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word.

Example 1:

Input:
board = [
  ["a","b","c","d"],
  ["s","a","a","t"],
  ["a","c","k","e"],
  ["a","c","d","n"]
],
words = ["bat","cat","back","backend","stack"]

Output: ["cat","back","backend"]

Solution

class TrieNode:
    def __init__(self):
        self.children = {} # alphabet -> TridNode
        self.endOfWord = False

class Solution:
    def __init__(self):
        self.root = TrieNode()
    
    def addWord(self, word: str):
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.endOfWord = True

    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        ROWS, COLS = len(board), len(board[0])
        
        # up, right, down, left
        DIRECTIONS = [[-1,0],[0,1],[1,0],[0,-1]]

        for word in words:
            self.addWord(word)
        
        res = set()
        visited = set()

        def dfs(r: int, c: int, node: TrieNode, word: str) -> None:
            if (r not in range(ROWS) or
                c not in range(COLS) or
                (r,c) in visited or
                board[r][c] not in node.children
                ):
                return
            
            visited.add((r,c))
            next_node = node.children[board[r][c]]
            next_word = word + board[r][c]
            if next_node.endOfWord:
                res.add(next_word)
            
            for dr, dc in DIRECTIONS:
                nr, nc = dr + r, dc + c
                dfs(nr, nc, next_node, next_word)
            
            visited.remove((r,c))
        
        for r in range(ROWS):
            for c in range(COLS):
                dfs(r, c, self.root, '')
        
        return list(res)