Python拼写检查器：如何在make_suggestions中复用已构建的三叉搜索树

问题核心 #

Spellchecker构造函数中构建的三叉搜索树仅为局部变量，无法在make_suggestions方法中复用，导致当前代码新建空树调用contains无法完成有效单词校验。需要将构造好的三叉树赋值为类实例属性，供后续方法调用。

修改方案 #

仅需修改带有### TODO: YOUR CODE HERE ###标记的两个方法：

1. 修改Spellchecker.__init__ #

将局部变量tree改为类实例属性self.tree，保存构建好的三叉树：

def __init__(self, valid_words):
    ### TODO: YOUR CODE HERE ###
    self.tree = TernarySearchTree()  # 改为self.tree，作为类属性保存

    for word in valid_words:
        self.tree.root_node = self.tree.insert(word, self.tree.root_node)

2. 修改Spellchecker.make_suggestions #

删除新建空三叉树的代码，直接调用类实例属性self.tree的contains方法进行校验：

def make_suggestions(self, word):
    ### TODO: YOUR CODE HERE ###
    nearby_strings_list = self.getNearbyStrings(word)
    edit_distance1_list = []

    # 移除新建空树的代码，直接使用已构建好的self.tree
    for i in nearby_strings_list:
        if self.tree.contains(i, self.tree.root_node):
            edit_distance1_list.append(i)
                  
    return edit_distance1_list

完整修改后代码 #

valid_words = ['the', 'of', 'and', 'to', 'a', 'in', 'for', 'is', 'on', 'that']

class Node:
   def __init__(self, value):
        self.left_child = None
        self.middle_child = None
        self.right_child = None
        self.value = value
        self.is_end = False

class TernarySearchTree:
    def __init__(self):
        self.root_node = None

    def insert(self, word, node=None):
        ### TODO: YOUR CODE HERE ###    
        if len(word) == 0:
            return node
        
        head = word[0]
        tail = word[1:]
        if node is None:
            node = Node(head)
    
        if head < node.value:
            node.left_child = self.insert(word, node.left_child)
        elif head > node.value:
            node.right_child = self.insert(word, node.right_child)
        else:
            if len(tail) == 0:
              node.is_end = True
            else:
              node.middle_child = self.insert(tail, node.middle_child)
                
        return node
            
    def contains(self, word, node=None):
        ### TODO: YOUR CODE HERE ###        

        if node is None or len(word) == 0:
          return False

        head = word[0]
        tail = word[1:]

        if (head < node.value) :
          return self.contains(word, node.left_child)
        elif (head > node.value) :
          return self.contains(word, node.right_child)
        else:
          if len(tail) == 0 and node.is_end:
            return True
          return self.contains(tail, node.middle_child)

class Spellchecker:
    def __init__(self, valid_words):
        ### TODO: YOUR CODE HERE ###
        self.tree = TernarySearchTree()

        for word in valid_words:
          self.tree.root_node = self.tree.insert(word, self.tree.root_node)
          
    def getNearbyStrings(self, word):
        letters    = 'abcdefghijklmnopqrstuvwxyz'
        splits     = [(word[:i], word[i:])    for i in range(len(word) + 1)]
        deletes    = [L + R[1:]               for L, R in splits if R]
        transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]
        replaces   = [L + c + R[1:]           for L, R in splits if R for c in letters]
        inserts    = [L + c + R               for L, R in splits for c in letters]
        return list(set(deletes + transposes + replaces + inserts))

    def make_suggestions(self, word):
        ### TODO: YOUR CODE HERE ###
        nearby_strings_list = self.getNearbyStrings(word)
        edit_distance1_list = []

        for i in nearby_strings_list:
          if self.tree.contains(i, self.tree.root_node):
            edit_distance1_list.append(i)
                  
        return edit_distance1_list

spellchecker = Spellchecker(valid_words)
output = spellchecker.make_suggestions(input())
output.sort()
for word in output:
    print(word)

内容的提问来源于stack exchange，提问作者Orihime_Orion