[Java] LeetCode 208. Implement Trie (Prefix Tree)

[Java] LeetCode 208. Implement Trie (Prefix Tree)

 

문   제 : 

Prefix Tree 클래스를 구현하여라.

 

 

Constraint

{ 1 <= word.length, prefix.length <= 2000 }

{ words and prefix consist only of lowercase En. }

{ At most 3*10^4 calls in total will be made to insert, search, and startswith. }

 

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.

void insert(String word) Inserts the string word into the trie.

boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.

boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

 

Example )

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

 

---

접   근 : 

HashSet을 이용해 검사

---

해   결 : 

Trie class에 HashSet을 멤버변수로 둔다.

 

생성자 함수

HashSet 을 초기화한다.

 

삽입 함수 : insert(String word)

HashSet에 word를 삽입한다.

 

검색 함수 : search(String word)

HashSet의 contains 메소드를 활용하여 word가 있는지 없는지 검사한다.

 

prefix 검색 함수 : startsWith(String prefix)

String 에 이미 존재하는 함수 startsWith를 이용해 HashSet에 있는 단어들을 모두 검사한다.

 

---

결   과  :

class Trie {
    HashSet<String> tree;

    public Trie() {
        tree = new HashSet<>();
    }
    
    public void insert(String word) {
        // tree에 삽입
        tree.add(word);
    }
    
    public boolean search(String word) {
        // word 찾기
        if(tree.contains(word)) return true;

        return false;
    }
    
    public boolean startsWith(String prefix) {
        for(String s: tree){
            if(s.startsWith(prefix)) return true;
        }
        return false;
    }
}

/**
 * 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);
 */