트라이(Trie)

• why?
  정수나 실수형 변수는 크기가 정해져 있으므로 비교에 상수 시간이 걸리지만,
  문자열 변수를 비교하는 데는 문자열의 길이에 비례하는 시간이 걸린다
  이러한 문제를 해결하기 위해 고안된 문자열 특화 자료구조의 대표적인 예가 트라이.

트라이 (Trie)

출처 : 위키피디아

    class TrieNode {
        //자식 노드 맵
        private Map<Character, TrieNode> childNodes = new HashMap<>();
        //마지막 글자 여부
        private boolean isLastChar;

        Map<Character, TrieNode> getChildNodes() {
            return this.childNodes;
        }

        boolean isLastChar() {
            return this.isLastChar;
        }

        void setLastChar(boolean isLastChar) {
            this.isLastChar = isLastChar;
        }

        boolean delete(String word, int index) {
            TrieNode node = childNodes.get(word.charAt(index));

            if (node == null) return false;

            if (index == word.length() - 1) {
                if (!node.isLastChar) return false;

                node.isLastChar = false;

                if (node.childNodes.size() == 0) {
                    this.childNodes.remove(target);
                }

                return true;
            }

            return node.delete(word, index + 1);
        }
    }

    class Trie {
        private TrieNode rootNode;

        Trie() {
            rootNode = new TrieNode();
        }

        void insert(String word) {
            TrieNode thisNode = this.rootNode;

            for (int i = 0; i < word.length(); i++) {
                thisNode = thisNode.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
            }
            thisNode.setLastChar(true);
        }

        boolean contains(String word) {
            TrieNode node = this.rootNode;

            for (int i = 0; i < word.length(); i++) {
                node = node.getChildNodes().get(word.charAt(i));

                if (node == null)
                    return false;
            }

            return node.isLastChar();
        }

        //삭제 성공시 true, 실패시 false 반환 (해당 문자열이 없는 경우)
        boolean delete(String word) {
            return rootNode.delete(word, 0);
        }
    }

연습문제 : 백준 5670번, 프로그래머스 2020 KAKAO BLIND RECRUITMENT '가사 검색'