208-트 리 구현(접두사 트 리)

머리말
접두사 트 리 는 우리 가 자주 사용 하 는 데이터베이스 색인 과 같은 자주 사용 하 는 데이터 구조 이다.그리고 접두사 나무 에 대한 소 개 는 LeetCode 중국 에 접두사 나무 에 관 한 튜 토리 얼 이 있 기 때문에 저 는 도끼 질 을 하지 않 겠 습 니 다.제 답 도 튜 토리 얼 의 방향 을 참고 하여 풀 겠 습 니 다.여러분 께 참고 가 되 기 를 바 랍 니 다.다음은 원제:
insert,search,starts With 세 동작 을 포함 하 는 Trie(접두사 트 리)를 실현 합 니 다.
예제:Trie trie=new Trie();
trie.insert("apple");trie.search("apple"); // truetrie.search("app")를 되 돌려 줍 니 다.//falsetrie.startsWith("app");/truetrie.insert("app")를 되 돌려 줍 니 다.trie.search("app"); // true 설명 을 되 돌려 줍 니 다:
너 는 모든 입력 이 소문 자 a-z 로 구성 되 어 있다 고 가정 할 수 있다.모든 입력 이 비 어 있 는 문자열 임 을 보증 합 니 다.
문제 풀이 의 사고 방향.
4.567917.나 무 는 노드 로 구성 되 어 있 습 니 다.노드 정 의 는 노드 값(접두사 트 리 의 정의,값 은 문자 char)과 잎 노드 의 지침 을 포함 해 야 합 니 다.그러나 한 단어 인지 아 닌 지 를 식별 하기 위해 boolean 변 수 를 추가 합 니 다
4.567917.전체 소문 자(a-z)로 입력 한 것 을 알 고 있 기 때문에 길이 가 26 인 배열 로 잎 노드 를 저장 할 수 있 습 니 다.또한 a-z 의 ASCII 코드 는 연속 적 이 고 ASCII 는 97-123 이기 때문에 ASCII 코드-97=대응 하 는 노드 의 배열 아래 표 시 를 직접 사용 할 수 있 습 니 다
배열 기반 접두사 트 리
class Trie {
    /**
     *       
     */
    public char value;
    /**
     * a-z 26   ,       a ASCII  97,                   ASCII -97
     */
    public Trie[] children=new Trie[26];
    /**
     *                  
     */
    public boolean endAsWord=false;
    
    public Trie() {
        
    }
    /**
     *       
     * @param word   
     */
    public void insert(String word) {
        if(word!=null){
            //       
            char[] charArr=word.toCharArray();
            //      ,            
            Trie currentNode=this;
            for(int i=0;i

좋은 웹페이지 즐겨찾기