# # # @param operators string字符串二维数组 the ops # @return string字符串一维数组 # class Solution: def __init__(self): self.mark = {} def trieU(self , operators ): res = [] for operator in operators: if operator[0] == '1': self.insert(operator[1],self.mark) elif operator[0] == '2': self.delete(operator[1],self.mark) elif operator[0] == '3': contains = 'YES' if self.search(operator[1]) else 'NO' res.append(contains) elif operator[0] == '4': num = self.prefixNumber(operator[1]) res.append(str(num)) # print(self.mark) return res def search(self,word): if not word: return True root = self.mark for c in word: if c not in root: return False root = root[c] return '#' in root def prefixNumber(self,word): if not word: return 0 root = self.mark for c in word: if c not in root: return False root = root[c] def count(root): res = 0 for k,v in root.items(): if k=='#': res += 1 else: res += count(v) return res return count(root) def insert(self,word,root): if not word: root['#'] = {} return root c = word[0] root[c] = self.insert(word[1:], root.get(c,{})) return root def delete(self,word,root): # print(word,root) if not word : if '#' in root: root.pop('#') # print(root) return root c = word[0] if c not in root: return root root[c] = self.delete(word[1:], root.get(c,{})) return root