Tree

[Notes] Trees - Tries

Posted by 西维蜀黍的OJ Blog on 2023-09-10, Last Modified on 2023-11-13

Knowledge

题目

解析

208. Implement Trie (Prefix Tree)

  • 每个 TrieNode 节点都用一个hashmap来存储他的chidlen
class TrieNode:
	def __init__(self):
		self.children = {}
		self.endOfWord = False


class Trie:

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

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

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

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

ref

211. Design Add and Search Words Data Structure

  • 用DFS去实现回溯

class TrieNode:
	def __init__(self):
		self.children = {}  # a : TrieNode
		self.word = False


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

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

	def search(self, word: str) -> bool:
		def dfs(j, root):
			cur = root

			for i in range(j, len(word)):
				c = word[i]
				if c == ".":
					for child in cur.children.values():
						if dfs(i + 1, child):
							return True
					return False
				else:
					if c not in cur.children:
						return False
					cur = cur.children[c]
			return cur.word

		return dfs(0, self.root)

ref

2707. Extra Characters in a String

Ref

FEATURED TAGS
graph hashmap hashset leetcode linkedlist lintcode sortarray stack topic tree 剑指刷题 双指针 快慢指针

TOC