class Trie {
    final int ALPHABET_SIZE = 26;         // 포인터 배열의 길이(표현할 수 있는 문자 개수)

    class Node {
        Node[] children = new Node[ALPHABET_SIZE];     
        boolean isEndOfWord;              // 저장하려는 문자열의 마지막 문자 여부

        public Node() {
            for (int i=0; i<ALPHABET_SIZE; i++) {
                children[i] = null;       // 포인터 배열 초기화
            }

            isEndOfWord = false;          // 마지막 문자 여부 초기화
        }
    }

    Node root;                            // 문자열의 첫번째 문자

    public void insert(String key) {
        int length = key.length();        // 탐색하려는 문자열 길이
        int alphabetIdx;                  // 문자열의 각 문자의 인덱스
        Node curAlphabet = root;          // 현재 탐색중인 문자열의 문자

        for (int level=0; level<length; level++) {
            alphabetIdx = key.charAt(level) - 'a';                    // 문자열의 각 문자의 인덱스 구하기
            Node nextAlphabet = curAlphabet.children[alphabetIdx];    // 문자열의 다음 문자

            if (nextAlphabet == null) {         // 찾으려는 문자에 연결된 자식 노드가 없을 경우
                nextAlphabet = new Node();      // 새로운 노드 생성 뒤 자식 노드로 연결
            }

            curAlphabet = nextAlphabet;         // 찾으려는 문자의 자식 노드를 현재 노드로
        }

        curAlphabet.isEndOfWord = true;         // 문자열의 모든 문자에 대해 삽입이 끝났다면 마지막 문자의 노드는 true로 변경하여 하나의 문자열이 저장됐음을 표시
    }

    public boolean search(String key) {
        int length = key.length();        // 탐색하려는 문자열 길이
        int alphabetIdx;                  // 문자열의 각 문자의 인덱스
        Node curAlphabet = root;          // 현재 탐색중인 문자열의 문자

        for (int level=0; level<length; level++) {
            alphabetIdx = key.charAt(level) - 'a';
            Node nextAlphabet = curAlphabet.children[alphabetIdx];

            if (nextAlphabet == null) {         // 탐색하려는 문자열이 존재하지 않는 경우
                return false;
            }

            curAlphabet = nextAlphabet;         // 찾으려는 문자의 자식 노드를 현재 노드로
        }

        return (curAlphabet.isEndOfWord);       // 탐색하려는 문자열이 존재하는 경우
    }
}