如何改變這種前綴特里返回包含類似前綴

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