박종훈 알고리즘 블로그

(Leetcode) 208 - Implement Trie (Prefix Tree)

기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.

https://neetcode.io/practice


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

내가 작성한 풀이

class Trie {

    Node root = new Node();

    public Trie() {

    }

    public void insert(String word) {
        Node currentNode = root;
        for(char c : word.toCharArray()) {
            if(currentNode.nodes[c - 97] == null) {
                currentNode.nodes[c - 97] = new Node();
            }
            currentNode = currentNode.nodes[c - 97];
        }
        currentNode.val = word;
    }

    public boolean search(String word) {
        Node currentNode = root;
        for(char c : word.toCharArray()) {
            if(currentNode.nodes[c - 97] == null) {
                return false;
            }
            currentNode = currentNode.nodes[c - 97];
        }

        return currentNode.val != null && currentNode.val.equals(word);
    }

    public boolean startsWith(String prefix) {
        Node currentNode = root;
        for(char c : prefix.toCharArray()) {
            if(currentNode.nodes[c - 97] == null) {
                return false;
            }
            currentNode = currentNode.nodes[c - 97];
        }
        return true;
    }
}

class Node {
    String val;
    Node[] nodes = new Node[26];
}

TC, SC

insert, search, startsWith 메소드의 경우 입력된 문자열의 길이를 n 이라 하였을 때 시간 복잡도는 O(n)이다. 공간 복잡도는 insert된 문자열의 갯수N 이라 하고 insert된 문자열의 길이의 평균L이라고 하였을 때 O(N * L * 26)이다. 26은 계수이기 때문에 생략할 수 있다.

categories: 스터디-알고리즘

tags: 자바 , java , 리트코드 , Leetcode , 알고리즘 , trie , tree , prefix