Trie前缀树

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。

构造前缀树

```class Node:
def __init__(self):
self.is_last = False
self.children = {}
def __repr__(self):
return 'Node({},[{}])'.format(self.is_last,
','.join('{}:{}'.format(x, repr(self.children[x])) for x in self.children))
```

```class Trie:
def __init__(self):
self.root = Node()```

```class Trie:
def __init__(self):
self.root = Node()

def generate_node(self, word:str) -> Node:
node = Node()
if len(word) > 0:
node.children[word[0]] = self.generate_node(word[1:])
else:
node.is_last = True
return node
```

```class Trie:
def __init__(self):
self.root = Node()

def generate_node(self, word:str) -> Node:
#...

def get_node_rest(self, root:Node, word:str)-> tuple:
if not word:
return root, ''
elif word[0] in root.children:
return self.get_node_rest(root.children[word[0]], word[1:])
else:
return root, word```

```#前缀树
class Node:
def __init__(self):
self.is_last = False
self.children = {}
def __repr__(self):
return 'Node({},[{}])'.format(self.is_last,
','.join('{}:{}'.format(x, repr(self.children[x])) for x in self.children))

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

def generate_node(self, word:str) -> Node:
node = Node()
if len(word) > 0:
node.children[word[0]] = self.generate_node(word[1:])
else:
node.is_last = True
return node

def get_node_rest(self, root:Node, word:str)-> tuple:
if not word:
return root, ''
elif word[0] in root.children:
return self.get_node_rest(root.children[word[0]], word[1:])
else:
return root, word

def insert(self, word):
node, rest = self.get_node_rest(self.root, word)
if rest:
node.children[rest[0]] = self.generate_node(rest[1:])
else:
node.is_last = True

def search(self, word):
node, rest = self.get_node_rest(self.root, word)
return rest == '' and node.is_last

def startsWith(self, word):
_, rest = self.get_node_rest(self.root, word)
return len(rest) == 0```

结语

0 条评论

相关文章

371

2695

1778

721

782

Go语言实战笔记（七）| Go 类型

Go 语言是一种静态类型的编程语言，所以在编译器进行编译的时候，就要知道每个值的类型，这样编译器就知道要为这个值分配多少内存，并且知道这段分配的内存表示什么。

763

23810

厕读：每日一题，面试无忧

4. 下列说法正确的有（） A． class中的constructor不可省略 B． constructor必须与class同名，但方法不能与class同名 C...

2806

java final 关键字

http://blog.csdn.net/niguang09/article/details/6035813

732