208. Implement Trie (Prefix Tree)

대체 뭐 어떻게 하는건지 감도 안왔었다.

결국 중요한건

 

1. 단어를 만들 때 각 알파뱃까지로 만들어진 객체가 있는지를 보고

2. 그 아래로 쭉쭉 만들어가면서 만들고

 

확인할 때에는

 

1. DFS 를 써서 확인할 단어로 보다가

2. 정확히 일치하면 맞는거

3. prefix 인 경우는 그거만 확인하면 됨

 

으로 진행하면 된다.

뭔가 지금까지 하면서 느낀게, 이런 구현들은 객체를 어떻게 만들지를 보는 것 같다.

요구조건에 따라 객체를 잘 만들면 해결 자체는 수월해 보임.

 

 

class Word {
    boolean isEnd;
    Word[] cha = new Word[26]; // a ~ z 까지, 그리고 그 내부로 들어가면 그것 또한 트리의 형태.
}

class Trie {
    // 처음부터 확인한다.
    // 노드로 해서 아래 트리 형태로 만들어간다.
    // 맨 마지막까지 일치해야 동일한 문자열임을 알 수 있다.
    // startsWith 면 끝까지 볼 필요 X
    Word root;

    public Trie() {
        root = new Word();
    }
    
    public void insert(String word) {
        Word worder = root;

        for(int i=0; i<word.length(); i++) {
            int now = word.charAt(i) - 'a';

            // 구조에서 현재 위치에 아직 들어간 데이터가 없다면 넣어주기
            if(worder.cha[now] == null) {
                // 그럼 어떤 Word 가 들어갈까? 그거는 거기서 확인해주면 된다.
                Word input = new Word();
                worder.cha[now] = input;

            } else {
                // 현재 위치에 이미 값이 존재한다면?
                // 그러면 그냥 옮기면 됨.
            }
            // 그 다음으로 가서 또 확인해주면 된다.
            worder = worder.cha[now];
        }

        worder.isEnd = true;
    }
    private boolean dfs(String word, int index, Word worder, boolean startsWith) {
        // 확인문자 끝까지 왔고, 시작확인하는거면 OK
        if(startsWith && word.length() == index) return true;

        // 확인문자나 문자가 끝까지 왔으면
        if(word.length() == index) {
            // 딱 일치하면 ㄱㅊ 아니면 false
            if(worder.isEnd) return true;
            else return false;
        }

        // 여기 하위 객체가 있다면 거기로 가서 확인한다.
        if(worder.cha[word.charAt(index) - 'a'] != null) {
            worder = worder.cha[word.charAt(index) - 'a'];
            return dfs(word, index+1, worder, startsWith);
        } else {
            return false;
        }
    }
    
    public boolean search(String word) {
        return dfs(word, 0, root, false);
    }
    
    public boolean startsWith(String prefix) {
        return dfs(prefix, 0, root, 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);
 */