如何改变这种前缀特里返回包含类似前缀

Question

你好，这是我的前缀特里代码部分的所有的话，我试图得到它的底部比只是前缀返回更多，更多的解释：

class TrieNode: 
    def __init__(self): 
     self.isString = False 
     self.children = {} 


def insertString(word, root): 
    currentNode = root 
    for char in word: 
     if char not in currentNode.children: 
      currentNode.children[char] = TrieNode() 
     currentNode = currentNode.children[char] 
    currentNode.isString = True 


def findStrings(prefix, node, results): 
    if node.isString: 
     results.append(prefix) 
    for char in node.children: 
     findStrings(prefix + char, node.children[char], results) 


def longestPrefix(word, root): 
    currentNode = root 
    currentPrefix = '' 
    for char in word: 
     if char not in currentNode.children: 
      break 
     else: 
      currentNode = currentNode.children[char] 
      currentPrefix += char 
    strings = [] 
    findStrings(currentPrefix, currentNode, strings) 
    return strings 
    pass 
    # Discussion: Is it dangerous to assume that findStrings actually found a string? 
    # Hint: There is an edge case that will break this 


wordList = ['aydt', 'coombs', 'schuhmacher', 'claypoole', 'exhume', 'forehands', 'carin', 'plaits', 'alfonsin', 
      'hometowns', 'pedestals', 'emad', 'hourly', 'purchaser', 'spogli', 'combativeness', 'henningsen', 'luedke', 
      'duchin', 'koglin', 'teason', 'bumpings', 'substantially', 'lamendola', 'cecola', 'henze', 'tutti', 'dills', 
      'satirical', 'jetted', 'intertwine', 'predict', 'breezes', 'cyclist', 'ancillary', 'schaumburg', 'viewer', 
      "bay's", 'emissions', 'kincheloe', 'trees', 'vipperman', 'exhale', 'ornamental', 'repeated', 'pedestal', 
      'pedesta', 'pedest'] 

root = TrieNode() 

for word in wordList: 
    insertString(word, root) 

allWords = [] 
findStrings('', root, allWords) 
print(allWords) 

inputWord = 'co' 
print(longestPrefix(inputWord, root)) 

inputWord = 'pedestals' 
print(longestPrefix(inputWord, root)) 

我想知道如何获得print(longestPrefix('pedestals', root))返回'基座'，'基座'，'pedesta'，'pedest'，而不仅仅是基座。我在代码中缺少什么？

Answer 1

我想了解如何获得打印（longestPrefix（ '基座'， 根））返回 '基座'， '基座'， 'pedesta'， 'pedest'，而不是仅仅 基座。

由于基座不是一个前缀，这没有任何意义给予代码的逻辑 - 我本来期望你想知道为什么​​没有返回这四个结果。我下面返工你的代码，把所有的功能集成到方法，因为每个被带你定义为参数的对象：

class TrieNode: 
    def __init__(self): 
     self.isString = False 
     self.children = {} 

    def insertString(self, word): 
     for char in word: 
      if char not in self.children: 
       self.children[char] = TrieNode() 
      self = self.children[char] 
     self.isString = True 

    def findStrings(self, prefix): 
     results = [] 
     if self.isString: 
      results.append(prefix) 

     for char in self.children: 
      results.extend((self.children[char]).findStrings(prefix + char)) 

     return results 

    def longestPrefix(self, word): 
     currentPrefix = '' 

     for char in word: 
      if char not in self.children: 
       break 
      else: 
       self = self.children[char] 
       currentPrefix += char 

     return self.findStrings(currentPrefix) 

wordList = [ 
    'aydt', 'coombs', 'schuhmacher', 'claypoole', 'exhume', 'forehands', 'carin', 'plaits', 'alfonsin', 
    'hometowns', 'pedestals', 'emad', 'hourly', 'purchaser', 'spogli', 'combativeness', 'henningsen', 'luedke', 
    'duchin', 'koglin', 'teason', 'bumpings', 'substantially', 'lamendola', 'cecola', 'henze', 'tutti', 'dills', 
    'satirical', 'jetted', 'intertwine', 'predict', 'breezes', 'cyclist', 'ancillary', 'schaumburg', 'viewer', 
    "bay's", 'emissions', 'kincheloe', 'trees', 'vipperman', 'exhale', 'ornamental', 'repeated', 'pedestal', 
    'pedesta', 'pedest' 
] 

root = TrieNode() 

for word in wordList: 
    root.insertString(word) 

allWords = root.findStrings('') 
print(allWords) 

inputWord = 'co' 
print(root.longestPrefix(inputWord)) 

inputWord = 'pedest' 
print(root.longestPrefix(inputWord)) 

最后两个print语句输出：

['coombs', 'combativeness'] 
['pedest', 'pedesta', 'pedestal', 'pedestals'] 

Answer 2

wordList = ['aydt', 'coombs', 'schuhmacher', 'claypoole', 'exhume', 'forehands', 'carin', 'plaits', 'alfonsin', 
      'hometowns', 'pedestals', 'emad', 'hourly', 'purchaser', 'spogli', 'combativeness', 'henningsen', 'luedke', 
      'duchin', 'koglin', 'teason', 'bumpings', 'substantially', 'lamendola', 'cecola', 'henze', 'tutti', 'dills', 
      'satirical', 'jetted', 'intertwine', 'predict', 'breezes', 'cyclist', 'ancillary', 'schaumburg', 'viewer', 
      "bay's", 'emissions', 'kincheloe', 'trees', 'vipperman', 'exhale', 'ornamental', 'repeated', 'pedestal', 
      'pedesta', 'pedest'] 

def findsubstring(fullstring): 
    for word in wordList: 
     if word in fullstring: 
      print (word) 

findsubstring("pedestals") 

输出：

pedestals 
pedestal 
pedesta 
pedest