Trie

A trie is a tree-like data structure whose nodes store the letters of an alphabet. By structuring the nodes in a particular way, words and strings can be retrieved from the structure by traversing down a branch path of the tree.
정의 : tree 형태의 자료구조로 각각의 노드들은 string의 한 알파벳을 저장한다.

장점 : BST(Binary Search Tree) 보다 빠른 검색시간

• O(M * logN) VS O(M)
  (M : String의 길이 , N 단어의 개수)

단점 : 공간복잡도가 크다 ( 단어 길이가 길어질때마다 알파벳 길이 개수의 trienode 추가)

• O( ALPHABET_SIZE * M * N )

구현 :

package org.example;

public class Trie {
    private static final int ALPHABET_SIZE = 26;

    private static class TrieNode{
        TrieNode[] children = new TrieNode[ALPHABET_SIZE];
        boolean isWord;

        TrieNode(){
            isWord = false;
            for(int i = 0 ; i< ALPHABET_SIZE;i++) children[i] = null;
        }
    }
    private TrieNode root = new TrieNode(); 

    public void insert(String key){
        //int level;
        int length = key.length();
        //int index;
        TrieNode temp = root;
        for(int level = 0; level<length; level++){
            int index = key.charAt(level) - 'a';
            if(temp.children[index] == null) temp.children[index] = new TrieNode();
            temp = temp.children[index];
        }
        temp.isWord = true;
    }

    public boolean search(String key){

        int length = key.length();
        TrieNode temp = root;

        for(int level  = 0; level<length; level++){
            int index = key.charAt(level) - 'a';
            if(temp.children[index] == null) return false;
            temp = temp.children[index];
        }
        return temp.isWord;
    }
}

관련 문제 :
https://programmers.co.kr/learn/courses/30/lessons/17685?language=java