>source

키가 문자, 즉 "D"이고 값이 다른 사전을 포함하는 객체에 대한 참조 인 여러 중첩 사전이 있습니다.

전의:

"DAD", "BAD", "DADDY"라는 단어의 경우 :

         B|D
         /  \
       A     A
      /       \
     D         D
    /          /\
   *          *  D
                  \
                   Y
                    \
                     *
If we are accessing "BAD"
    self.child = { B : ref to object, D : ref to object}
    self.child.get("B").child = { A : ref to object }
    self.child.get("B").child.get("A").child = { D : {}}

트리에 액세스하여 전체 트리 또는 입력 된 문자와 일치하는 부분 만 트리에서 모든 단어를 인쇄하려고합니다. 즉, "B"를 입력하면 "BAD"를 원하고 "D"를 입력하면 "DAD", "DADDY"를 원합니다.

현재 아래 코드는 예상대로 반환되지 않고 "D"를 입력하면 "DAD"와 "DY"가 반환됩니다.

자체 값은 클래스에서 초기에 초기화됩니다.

def traverseTree(self, dictionary, baseValue):
    for key, value in dictionary.items():
        if isinstance(value.child, dict):
            if not value.leaf:
                self.accum += key
            else:
                self.l.append(baseValue + (self.accum + key)
                self.accum = ''
            self.traverseTree(value.child, baseValue)

"DADDY"(DAD)의 첫 번째 덩어리는 그 값이 누산기로 밀리지 않기 때문에 잘려나 간 것 같습니다. 이 재귀 알고리즘을 사용하면 터미널 지점에 도달했기 때문에 각 노드를 방문하고 있다고 생각하지만 모든 단어 값을 재귀 적으로 액세스하고 저장하는 가장 좋은 방법은 무엇입니까?

MRE :


class Trie:
    def __init__(self):
        self.dict = {}
        self.terminate = False
    def insert(self, word):
        if len(word) == 0:
            self.terminate = True
        else:
            if word[0] in self.dict:
                self.dict[word[0]].insert(word[1:])
            else:
                self.dict[word[0]] = Trie()
                self.dict[word[0]].insert(word[1:])
    def terminal(self):
        if self.terminate:
            return True
    def autoSearch(self, toSearch):
        if toSearch == '':
            return self.traverseTreeTest()
    def traverseTreeTest(self):
        if self.terminate:
            return [""]
        returnval = []
        for key, children in self.dict.items():
            returnval.extend([key + rest for rest in children.traverseTreeTest()])
        return returnval
word = ["D","DAD", "B", "BAD", "DADDY", "Lad"]
x = Trie()
for y in word:
    x.insert(y)
print(x.autoSearch(''))

  • 답변 # 1

    문제는 모든 수준에서 업데이트하는 것입니다. self.lself.accum , 중첩 된 개체를 수정하므로 최상위 개체에서 전체 결과를 얻지 못합니다.

    다음은 객체를 수정하지 않고 모든 것을 목록으로 반환하는 버전입니다.

    def traverseTree(self):
        if self.leaf:
            return [""]
        returnval = []
        for key, value in self.child.items():
            returnval.extend([key + rest for rest in value.traverseTree()])
        return returnval
    
    

    이것은 기본적인 재귀입니다. 모든 케이스는 문자열 목록을 반환합니다. 기본 케이스는 리프로, 빈 문자열 만있는 목록을 반환합니다.

    재귀 케이스는 딕셔너리를 반복하며 키를 자식으로 재귀 한 결과에 접두사를 붙이고 모든 문자열 목록을 반환합니다.

관련 자료

  • 이전 javascript - vuejs - 전환 그룹 캐 러셀 애니메이션 한 번에 한 항목
  • 다음 excel : 생성 된 모든 통합 문서에 공통 워크 시트로 포함 할 워크 시트를 제외하고 개별 워크 시트를 내 보냅니다.