[Trie] Implement Trie (Prefix Tree)

Trie 구현(접두사 트리)

Implement Trie (Prefix Tree) - LeetCode

트리 ("try"로 발음) 또는 접두사 트리는 문자열 데이터세트에서 키를 효율적으로 저장하고 검색하는 데 사용되는 트리 데이터 구조입니다 . 자동 완성 및 맞춤법 검사기와 같은 이 데이터 구조의 다양한 응용 프로그램이 있습니다.

Trie 클래스를 구현합니다.

• Trie()trie 개체를 초기화합니다.
• void insert(String word)문자열을 word트라이에 삽입합니다.
• boolean search(String word)true문자열이 word트라이에 있는지(즉, 이전에 삽입되었는지) 반환하고 , false그렇지 않으면 반환합니다.
• boolean startsWith(String prefix)접두사가 있는 true이전에 삽입된 문자열이 있으면 반환 하고 그렇지 않으면 반환합니다 .wordprefixfalse

 

예시 1:

입력 
["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app 
" ], ["app"], ["app"], ["app"]] 출력 
[null, null, true, false, true, null, true] 설명 
Trie trie = new Trie(); 
trie.insert("사과"); 
trie.search("사과"); // True를 반환합니다. 
trie.search("app"); // False 반환 
trie.startsWith("app"); // True를 반환합니다. 
trie.insert("app"); 
trie.search("앱"); // 참을 반환

 

제약:

• 1 <= word.length, prefix.length <= 2000
• wordprefix영문 소문자로만 구성됩니다 .
• 총 최대 호출 횟수 는 3 * 10^4입니다.insert / search / startsWith.

---

class Trie {
    class TrieNode{
        boolean wordend=false;
        TrieNode child[] = new TrieNode[26];
    }
    
    TrieNode root=new TrieNode();
    public Trie() {}
    
    public void insert(String word) {
        TrieNode node=root,newnode=null;
        for(char ch: word.toCharArray()){
            if(node.child[ch-'a']==null) node.child[ch-'a']=newnode=new TrieNode();
            else newnode=node.child[ch-'a'];
            node=newnode;            
        }
        newnode.wordend=true;
    }
    
    public boolean search(String word) {
        TrieNode node = root;
        for(char ch: word.toCharArray()){
            if(node.child[ch-'a']==null) return false;
            node=node.child[ch-'a'];
        }
        return node.wordend;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for(char ch: prefix.toCharArray()){
            if(node.child[ch-'a']==null)return false;
            node=node.child[ch-'a'];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

Trie 자료구조는 맞춤법 검사 또는 자동완성 기능을 만들 때 사용할 수 있는 자료 구조 입니다.

먼저 단어를 추가하는 insert()를 구현해보면 Trie 자료구조의 시작은 무조건 root노드부터 시작을 합니다.

root노드의 value값은 따로 가지고 있지 않고 자식 노드를 가지고 있습니다.

 문자열을 순회하여 자식노드들을 추가해나가며 문자열의 마지막에 도달하면 마지막 문자라는 것을 알기 위해 wordend=true 값으로 설정한다.

 

문자열을 찾기위해 search()를 구현해보면 문자열을 순회하며 찾는 문자열의 마지막 문자의 wordend를 반환하여 문자열이 있는 지 찾을 수있습니다.

 

마지막으로 startWith()를 구현하여 입력된 문자열이 root노드 기준으로 자식노드를 모두 가지면 접두사가 있는 것이고 

하나라도 없으면 접두사를 가지지 않는 것으로 알 수 있습니다. 

이것은 search()메서드랑 구현이 똑같으며 반환 값이 문자열의 끝을 알 수 있는 값을 반환하는지 아니면 자식 노드가 있느지를 반환 하는지에 따라 search()와 startsWith() 나눌 수 있습니다.