.leetcode(208. Implement Trie (Prefix Tree))

문제

https://leetcode.com/problems/implement-trie-prefix-tree/

문제 풀기 전

1. Trie를 어렴풋하게 기억하기로는 단어별로 쪽개서 포도송이처럼 만드는 자료형이었다.
2. 이번에 제대로 구현해볼 기회가 생겼다고 생각했다.

직접 푼 풀이

소요시간: 24분(20:46 ~ 21:10)

class Trie {
    List<Trie> tries;
    char sub;
    boolean hasWord;


    /** Initialize your data structure here. */
    public Trie() {
        hasWord =false;
        tries = new ArrayList<>();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        Trie start = this;
        for (int i=0; i<word.length(); i++) {
            boolean hasChar = false;
            for (Trie each: start.tries) {
                if (each.sub == word.charAt(i)) {
                    start = each;
                    hasChar = true;
                    break;
                }
            }

            if (hasChar == false) {
                Trie newT = new Trie();
                newT.sub = word.charAt(i);
                start.tries.add(newT);
                start = newT;
            }
        }
        start.hasWord = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Trie start = this;
        for (int i=0; i<word.length(); i++) {
            boolean hasChar = false;
            for (Trie each: start.tries) {
                if (each.sub == word.charAt(i)) {
                    start = each;
                    hasChar = true;
                    break;
                } 
            }
            if (hasChar == false) {
                return false;
            }
        }
        return start.hasWord;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        Trie start = this;
        for (int i=0; i<prefix.length(); i++) {
            boolean hasChar = false;
            for (Trie each: start.tries) {
                if (each.sub == prefix.charAt(i)) {
                    start = each;
                    hasChar = true;
                    break;
                }
            }
            if (hasChar == false) {
                return false;
            }
        }
        return true;        
    }
}

느낀점

1. 좀 복잡하게 나왔는데 구성은 맞는것으로 보인다.
2. 솔루션은 TrieNode라는 클래스를 만들어 위 내용을 거의 정리하였고 제한설정인 26개의 알파벳을 이용해 List가 아닌 배열로 풀었던 점이 달랐다.

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)

나중에다시한번

• TrieNode를 만들어서 풀어보기