사전 트리 03 귀속 사전 트리에서 조회

1507 단어

Trie에서 단어 워드를 조회하는 귀속 해법


4
  • 귀속의 각도에서 보면 하나의 노드에서 알파벳을 찾는다

    • 4
  • 귀속 문제는 두 부분으로 나눌 수 있다. 규모가 더 작은 동일한 문제와 더 이상 축소할 수 없는 기본적인 문제이다.진입 규모가 더 작은 문제는 구속 조건이 있다.일단 규모가 더 작은 같은 문제에 들어가면 귀속체인에 들어가야 귀속체인에 들어가야 더 이상 축소할 수 없는 기본적인 문제에 도달할 수 있다

    • 4
  • 규모가 더 작은 것과 같은 문제는 다음 노드에서 다음 자모를 찾는 것이다.전제 조건은 현재 노드에서 첫 번째 자모를 찾았다는 것이다.만약 이 조건을 만족시키지 못한다면 첫 번째 노드에서 첫 번째 자모를 찾지 못했고 문제는 이미 끝났고 찾기에 실패했다는 것을 의미한다.이 조건을 만족시키고 귀속체인에 들어갔다

    • 4
  • 더 이상 축소할 수 없는 기본 상태는 첫 번째 노드에서부터word의 모든 자모를 찾았다는 것이다.한 걸음 더 나아가면 마지막 노드에서word를 찾은 후 존재하지 않는 자모를 찾는데 이 상태는 index==word이다.length();이때 검색 성공 여부를 판단하는 것은 마지막 노드의 isWord를 보는 것이다
    • /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
public boolean search(String word) {
    return search(root, word, 0);
}

//  word， ；
private boolean search(Node node, String word, int index) {
    if (index == word.length()) {
        return node.isWorld;
    }

    Character c = word.charAt(index);
    if (node.next.get(c) == null) {
        return false;
    }
    return search(node.next.get(c), word, index + 1);
}

    테스트 코드

    public static void main(String[] args) {
    WordDictionary dictionary = new WordDictionary();
    dictionary.addWord("apple");
    System.out.println(dictionary.search("apple"));
    System.out.println(dictionary.search("app"));
}

    출력:
    true false
    여러 가지 기타 응답/이동 문제 수정 또는 개선

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage