677.键值映射

677.键值映射

一、trie树

class TrieNode:
    def __init__(self):
        self.end = False         # 标志该字符是否为某个单词的结尾
        self.tns = [None] * 26   #记录该字符的后续字符，26个分支表示a-z，None表示无后续
        self.val = 0			 #记录值

class MapSum:

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

    def insert(self, key: str, val: int) -> None:
        i = self.root
        for s in key:
            j = ord(s) - ord('a')
            if i.tns[j] == None:
                i.tns[j] = TrieNode()
            i = i.tns[j]
        i.end = True
        i.val = val

    def sum(self, prefix: str) -> int:
        # 辅助函数，dfs遍历
        def dfs(root):
            # 操作外部变量
            nonlocal total
            if root == None:
                return
            if root.end:
                total += root.val
            for child in root.tns:
                dfs(child)

        
        # 先到达prefix结尾在Trie树的节点
        i = self.root
        for s in prefix:
            j = ord(s) - ord('a')
            if i.tns[j] == None:	# 如果中间有None，说明prefix不存在于树中
                return 0
            i = i.tns[j]
		# 全局变量统计val总和
        total = 0
		# 从i节点开始dfs遍历树
        dfs(i)
        return total

sum的dfs方法也可以用global关键字访问外部变量

def sum(self, prefix: str) -> int:
    # 辅助函数，dfs遍历
    def dfs(root):
        # 全局变量
        global total
        if root == None:
            return
        if root.end:
            total += root.val
        for child in root.tns:
            dfs(child)

    i = self.root
    for s in prefix:
        j = ord(s) - ord('a')
        if i.tns[j] == None:
            return 0
        i = i.tns[j]
    # 全局变量
    global total
    total = 0

    dfs(i)
    return total

二、

class MapSum:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.hash = {}

    def insert(self, key: str, val: int) -> None:
        self.hash[key] = val
        self.hash = dict(sorted(self.hash.items(), key = lambda x : x[0]))

    def sum(self, prefix: str) -> int:
        res = 0
        hasFinded = False
        for key in self.hash:
            if key[ : len(prefix)] == prefix:
                res += self.hash[key]
        return res