데이터 구조 와 알고리즘 - Trie 트 리

기초 지식
콘 셉 트
접두사 트 리, 사전 트 리, 단어 찾기 트 리 나 키 트 리 라 고도 합 니 다.나무 구조, 해시 나무의 변종.트 리 의 경로 에 저 장 된 것 은 문자 이 고 노드 에 저 장 된 것 은 현재 노드 를 마지막 으로 하 는 문자열 의 개수 입 니 다.
성질:

뿌리 노드 는 문 자 를 포함 하지 않 고 뿌리 노드 를 제외 한 모든 노드 는 하나의 문자 만 포함 합 니 다.

뿌리 노드 에서 특정한 노드 까지 경로 에 있 는 문 자 를 연결 하여 이 노드 에 대응 하 는 문자열 입 니 다.

각 노드 의 모든 하위 노드 에 포 함 된 문 자 는 같 지 않다.

전형 적 인 응용

특정한 문자열 이 있 는 지 확인 할 수 있 습 니 다. (노드 에 속성 을 추가 하여 현재 노드 를 마지막 으로 하 는 문자열 의 횟수 를 통계 하 는 데 사용 합 니 다)

특정한 문자열 을 접두사 로 하 는 문자열 의 개 수 를 통계 합 니 다 (노드 에 속성 을 추가 하여 이 노드 를 거 친 횟수 를 통계 합 니 다)

대량의 문자열 을 통계 하고 정렬 하 는 데 사용 되 며 (문자열 에 만 국한 되 지 않 음) 검색엔진 시스템 에서 텍스트 주파수 통계 에 자주 사용 된다.

장점.

불필요 한 문자열 을 최대한 줄 이 고 조회 효율 이 해시 표 보다 높다.

공간 을 크게 압축 하고 많은 공간 을 재 활용 할 수 있 으 며 복잡 도와 샘플 의 양 이 관계 가 있다

핵심 사상
공간 교환.문자열 의 공공 접 두 사 를 이용 하여 조회 시간의 비용 을 낮 추어 효율 을 높이 는 목적 을 달성 하 다. 
사고의 방향 을 세우다.
모든 노드 가 문자 라면 모든 노드 는 26 개의 자모 와 연 결 될 수 있 습 니 다. 이 를 위해 모든 노드 에 경로 의 노드 와 끝 노드, 그리고 연결 배열 을 기록 해 야 합 니 다.
응용 문제
1、208. Implement Trie (Prefix Tree)
Implement a trie with  insert ,  search , and  startsWith  methods.
Example:

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Note:

You may assume that all inputs are consist of lowercase letters  a-z .

All inputs are guaranteed to be non-empty strings.

class Trie {
    
    public class Node{
        int path; //             
        int end;  //              
        Node[] nexts;  //                
        
        public Node(){
            path = 0;
            end = 0;
            nexts = new Node[26];
        }
    }
    
    private Node node;
    /** Initialize your data structure here. */
    public Trie() {
        node = new Node();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        if(word == null)
            return;
        char[] str = word.toCharArray();
        Node root = node;
        int index = 0;
        for(int i = 0; i < str.length; i++){
            index = str[i] - 'a';
            if(root.nexts[index] == null)
                root.nexts[index] = new Node();
            root.path++;
            root = root.nexts[index];
        }
        root.end++;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        if(word == null)
            return false;
        char[] str = word.toCharArray();
        Node root = node;
        int index = 0;
        for(int i = 0; i < str.length; i++){
            index = str[i] - 'a';
            if(root.nexts[index] == null)
                return false;
             root = root.nexts[index];
        }
        return root.end == 0 ? false : true;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        if(prefix == null)
            return false;
        char[] str = prefix.toCharArray();
        Node root = node;
        int index = 0;
        for(int i = 0; i < str.length; i++){
            index = str[i] - 'a';
            if(root.nexts[index] == null)
                return false;
            root = root.nexts[index];
        }
        return true;
    }
}

211. Add and Search Word - Data structure design
Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters  a-z  or  . . A  .  means it can represent any one letter.
Example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note: You may assume that all words are consist of lowercase letters  a-z .

class WordDictionary{
    
    private Node root;

    public WordDictionary() {
        root = new Node((char) 0);
    }
    
    //*** Create Trie tree
    public void addWord(String word) {
        Node node = root;
        char[] arr = word.toCharArray();
        for(char ch : arr){
            Node child = node.children.get(ch);
            if(child == null){
                child = new Node(ch);
                node.children.put(ch, child);
            }
            node = child;
        }
    
        //*** Mark the end ot the worn in tree
        node.children.put(null, null);
    }
    
    public boolean search(String word) {
        char[] arr = word.toCharArray();
        return search(arr, 0, root);
    }
    
    //*** Recursive method to find word in the Trie tree
    private boolean search(char[] arr, int pos, Node node){
        
        //*** False -> if this is not the end of the word in the tree
        if(node == null || node.children == null)
            return false;
        if(pos == arr.length)
            return node.children.containsKey(null);
        
        //*** If it's a point -> find all possibilities
        if(arr[pos] == '.'){
            for(Character ch : node.children.keySet()){
                if(search(arr, pos+1, node.children.get(ch)))
                    return true;
            }
            return false;
        } else {
            
            //*** If it's not a point -> find the next character
            return search(arr, pos+1, node.children.get(arr[pos]));
        }
    }
    
    private class Node {
        char ch;
        Map children;
        public Node(char ch){
            this.ch = ch;
            children = new HashMap<>();
        }
    }
}