Last active
August 18, 2020 09:11
-
-
Save idiomer/bfecc1d3a397bda32673f38f918d0212 to your computer and use it in GitHub Desktop.
用点来访问dict里面的key
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class dotdict(dict): | |
"""dot.notation access to dictionary attributes""" | |
__getattr__ = dict.get | |
__setattr__ = dict.__setitem__ | |
__delattr__ = dict.__delitem__ | |
class TrieTree: | |
""" 字典树 """ | |
class Node: | |
def __init__(self, char, is_word=False): | |
self.char = char # 可以存char也可以不存char,冗余 | |
self.is_word = is_word | |
self.children = dict() | |
def __init__(self, words=None): | |
self.root = Node('') | |
if not (words is None or isinstance(words, str)): | |
self.add_word_list(words) | |
def add_word(self, word): | |
''' 添加word到TrieTree中 | |
''' | |
if len(word) == 0: | |
return | |
cur_node = self.root | |
for ch in word: | |
if ch not in cur_node.children: | |
cur_node.children[ch] = Node(ch) | |
cur_node = cur_node.children[ch] | |
cur_node.is_word = True | |
def add_word_list(self, words): | |
''' 批量添加word到TrieTree中 | |
''' | |
for word in words: | |
self.add_word(word) | |
def exists_word(self, word): | |
''' 给定word,判断这个word是否存在TrieTree中 | |
''' | |
cur_node = self.root | |
for ch in word: | |
if ch not in cur_node.children: | |
return False | |
cur_node = cur_node.children[ch] | |
if cur_node.is_word: | |
return True | |
else: | |
return False | |
def search_all(self, text, only_match_longest=False): | |
''' 给定text,返回text中所有的words(string多模式匹配) | |
only_match_longest=True未实现,前缀相同容易实现,后缀相同较难(需要额外的数据结构辅助) | |
''' | |
words = [] | |
for i in range(len(text)): | |
cur_node = self.root | |
for j in range(i, len(text)): | |
ch = text[j] | |
if ch not in cur_node.children: | |
break | |
if cur_node.children[ch].is_word: | |
words.append(text[i:j+1]) | |
cur_node = cur_node.children[ch] | |
return words |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment