Skip to content

Trie Advanced

Table of Contents

676. Implement Magic Dictionary

  • LeetCode | 力扣

  • Tags: Hash Table, String, Depth First Search, Design, Trie

212. Word Search II

from typing import List

from leetpattern.utils import Trie


# Backtracking + Trie
def findWords(board: List[List[str]], words: List[str]) -> List[str]:
    trie = Trie()
    for word in words:
        trie.add_word(word)

    m, n = len(board), len(board[0])
    result, visit = set(), set()

    def dfs(r, c, node, word):
        if (
            r < 0
            or r >= m
            or c < 0
            or c >= n
            or (r, c) in visit
            or board[r][c] not in node.children
        ):
            return None

        visit.add((r, c))

        node = node.children[board[r][c]]
        word += board[r][c]
        if node.is_word:
            result.add(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(m):
        for c in range(n):
            dfs(r, c, trie.root, "")

    return list(result)


def test_find_words():
    board = [
        ["o", "a", "a", "n"],
        ["e", "t", "a", "e"],
        ["i", "h", "k", "r"],
        ["i", "f", "l", "v"],
    ]
    words = ["oath", "pea", "eat", "rain"]
    result = findWords(board, words)
    assert sorted(result) == ["eat", "oath"]

3093. Longest Common Suffix Queries

3045. Count Prefix and Suffix Pairs II

  • LeetCode | 力扣

  • Tags: Array, String, Trie, Rolling Hash, String Matching, Hash Function

336. Palindrome Pairs

1948. Delete Duplicate Folders in System

  • LeetCode | 力扣

  • Tags: Array, Hash Table, String, Trie, Hash Function

425. Word Squares 👑

527. Word Abbreviation 👑

588. Design In-Memory File System 👑

from collections import defaultdict


class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.content = ""


# Trie
class FileSystem:

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

    def ls(self, path: str) -> list:
        cur = self.root

        if path != "/":
            paths = path.split("/")[1:]
            for p in paths:
                cur = cur.children[p]
        if cur.content:
            return [path.split("/")[-1]]

        return sorted(cur.children.keys())

    def mkdir(self, path: str) -> None:
        cur = self.root
        paths = path.split("/")[1:]
        for p in paths:
            cur = cur.children[p]

    def addContentToFile(self, filePath: str, content: str) -> None:
        cur = self.root
        paths = filePath.split("/")[1:]
        for p in paths:
            cur = cur.children[p]
        cur.content += content

    def readContentFromFile(self, filePath: str) -> str:
        cur = self.root
        paths = filePath.split("/")[1:]
        for p in paths:
            cur = cur.children[p]
        return cur.content


obj = FileSystem()
obj.mkdir("/a/b/c")
obj.addContentToFile("/a/b/c/d", "hello")
print(obj.ls("/"))  # ["a"]
print(obj.readContentFromFile("/a/b/c/d"))  # "hello"

616. Add Bold Tag in String 👑

  • LeetCode | 力扣

  • Tags: Array, Hash Table, String, Trie, String Matching

758. Bold Words in String 👑

  • LeetCode | 力扣

  • Tags: Array, Hash Table, String, Trie, String Matching

642. Design Search Autocomplete System 👑

  • LeetCode | 力扣

  • Tags: String, Depth First Search, Design, Trie, Sorting, Heap Priority Queue, Data Stream

1065. Index Pairs of a String 👑

1166. Design File System 👑

from collections import defaultdict


class TrieNode:
    def __init__(self, name):
        self.name = name
        self.children = defaultdict(TrieNode)
        self.value = -1


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

    def createPath(self, path: str, value: int) -> bool:
        paths = path.split("/")[1:]
        cur = self.root

        for idx, path in enumerate(paths):
            if path not in cur.children:
                if idx == len(paths) - 1:
                    cur.children[path] = TrieNode(path)
                else:
                    return False
            cur = cur.children[path]

        if cur.value != -1:
            return False
        cur.value = value
        return True

    def get(self, path: str) -> int:
        cur = self.root
        paths = path.split("/")[1:]

        for path in paths:
            if path not in cur.children:
                return -1
            cur = cur.children[path]

        return cur.value


# Your FileSystem object will be instantiated and called as such:
path = "/a"
value = 1
obj = FileSystem()
print(obj.createPath(path, value))  # False
print(obj.get(path))  # 1

1858. Longest Word With All Prefixes 👑