문제

https://leetcode.com/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-interview-150

해결 방법 1

• Trie의 기능을 구현하는 문제

1. Trie 선언
   • HashMap을 사용하여 현재 Node에서 다음 Node(자식)가 특정 문자를 포함하는지와 포함한다면 다음 Node를 가리키게 함
   • 현재 Node가 문자열의 마지막인지도 체크해줘야 함
2. Trie에 문자열 삽입
   • root Node 부터 시작하여 현재 Node의 자식에 다음 문자가 있는지 체크
   • 있으면 다음 Node로 이동
   • 없으면 새로운 Node 추가
   • 위 방식으로 진행 후 마지막 문자에는 이 문자가 마지막 문자라고 체크
3. Trie에서 문자열 검색
   • root Node 부터 시작하여 현재 Node의 자식에 다음 문자가 있는지 체크
   • 있으면 다음 Node로 이동
   • 없으면 false return
   • 입력된 문자열 끝까지 진행 후 문자열의 마지막 문자가 Trie에서 마지막 문자라면 true return
4. Trie에서 특정 문자열로 시작하는 문자열이 있는지 검색
   • 문자열 검색과 같은 로직이지만 문자열의 마지막 문자가 Trie에서 마지막 문자가 아니여도 true return

코드

class Trie {

    private Node root;

    public Trie() {
        this.root = new Node();
    }
    
    public void insert(String word) {
        Node current = this.root;

        for (char c : word.toCharArray()) {
            if (!current.children.containsKey(c)) {
                current.children.put(c, new Node());
            }
            current = current.children.get(c);
        }
        current.isEndOfWord = true;
    }

    static Node current;
    
    public boolean search(String word) {
        if (!startsWith(word)) return false;
        return current.isEndOfWord;
    }
    
    public boolean startsWith(String prefix) {
        current = this.root;

        for (char c : prefix.toCharArray()) {
            if (!current.children.containsKey(c)) return false;

            current = current.children.get(c);
        }
        return true;
    }
}

class Node {
    Map<Character, Node> children;
    boolean isEndOfWord;

    Node() {
        this.children = new HashMap<>();
        this.isEndOfWord = false;
    }
}

결과

해결 방법 2

• 해결 방법 1을 통해 해결 했지만, 시간과 메모리 효율을 향상시킬 방법을 생각해 봄
• HashMap을 통해 Character을 저장하는 방식으로 Trie를 구성했지만, 문제에서는 알파벳 소문자만 입력된다고 했기 때문에 HashMap 대신 26칸짜리 배열을 사용하면 더 효율적일 수 있다고 생각함

코드

class Trie {

    private Node root;

    public Trie() {
        this.root = new Node();
    }
    
    public void insert(String word) {
        Node current = this.root;

        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (current.children[idx] == null) {
                current.children[idx] = new Node();
            }
            current = current.children[idx];
        }
        current.isEndOfWord = true;
    }

    static Node current;
    
    public boolean search(String word) {
        if (!startsWith(word)) return false;
        return current.isEndOfWord;
    }
    
    public boolean startsWith(String prefix) {
        current = this.root;

        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (current.children[idx] == null) return false;

            current = current.children[idx];
        }
        return true;
    }
}

class Node {
    Node[] children;
    boolean isEndOfWord;

    Node() {
        this.children = new Node[26];
        this.isEndOfWord = false;
    }
}

결과

• 배열을 사용한 경우 시간, 메모리 적으로 더 효율적으로 해결할 수 있었음