python字典树有两个点超时
查看原帖
python字典树有两个点超时
134597
Rex_HH楼主2024/5/14 16:33

下面是我的代码,是我的代码写的有问题还是python字典树都不行?


class TrieNode(object):
    def __init__(self, value=None, parent=None, isend=False):
        # 值
        self.value = value
        # 父结点
        self.parent = parent
        # 子节点,{value:TrieNode}
        self.children = {}
        # 结尾标记
        self.isend = isend
        # 查找标记
        self.hassearch = False


class Trie(object):
    def __init__(self):
        # 创建空的根节点
        self.root = TrieNode()

    def insert(self, sequence):
        """
        基操,插入一个序列
        :param sequence: 列表
        :return:
        """
        cur_node = self.root
        for item in sequence:
            if item not in cur_node.children:
                # 插入结点
                child = TrieNode(value=item, parent=cur_node)
                cur_node.children[item] = child
                cur_node = child
            else:
                # 更新结点
                cur_node = cur_node.children[item]
        cur_node.isend = True

    def search(self, sequence):
        """
        基操,查询是否存在完整序列
        :param sequence: 列表
        :return:
        """
        cur_node = self.root
        mark = "OK"
        for item in sequence:
            if item not in cur_node.children:
                mark = "WRONG"
                break
            else:
                cur_node = cur_node.children[item]
        # 如果还有子结点,说明序列并非完整
        if not cur_node.isend:
            mark = "WRONG"
        else:
            if cur_node.hassearch:
                mark = "REPEAT"
            else:
                cur_node.hassearch = True
        return mark

if __name__ == "__main__":
    trie = Trie()

    n = int(input().strip())
    for _ in range(n):
        s = input().strip()
        trie.insert(s)

    m = int(input().strip())
    for _ in range(m):
        s = input().strip()
        markx = trie.search(s)
        print(markx)
”“”
2024/5/14 16:33
加载中...