LeetCode알고리즘 Implement Trie (Prefix Tree)문제

오늘은 208번 Implement Trie문제를 풀어보겠습니다.
난이도는 중간이고 성공률은 52.1%네요.

일주일에 몇 개씩 풀고 있는데 이 문제가 첫 번째 페이지의 마지막 문제였어요.
물론 번호 왼쪽에 체크가 아닌 물음표 표시도 꽤 보이네요.
시도는 했으나 실패했던 문제도 있어서 다시 풀어봐야 하지만 하기 싫은
언젠가는 풀겠지.. 화이팅

문제를 풀기 전에 트라이에 대한 개념을 정리해보려 합니다.
트라이는 탐색 트리의 일종이며, 트리 자료구조입니다. 
문자열 검색을 빠르게 해 주기로 유명합니다.
노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유하며, 루트는 빈 문자열에 연관됩니다.

문자열에 한 문자만 넣고 다음 문자는 자식 노드에서 찾도록 합니다.
즉 문자열은 세로로 저장되게 됩니다.
문자열이 다 똑같은 문자로 시작하는 것은 아니니 루트는 비워두고 시작합니다.
문자열의 최대 길이가 N이라고 가정하면 시간 복잡도는 O(N)이게 됩니다.

 

다시 문제로 돌아가 보겠습니다.
오늘은 트라이를 구현하는 문제입니다.

모든 입력은 소문자 a-z로 구성되어 있습니다.
모든 입력은 비어있지 않은 문자열이 보장됩니다.

기본적인 틀은 제공되고 트라이에 필요한 insert, search, startsWith메서드를 구현해야 합니다.

public class Trie {

    /** Initialize your data structure here. */
    public Trie() {
        
    }
    
    /** Inserts a word into the trie. */
    public void Insert(string word) {
        
    }
    
    /** Returns if the word is in the trie. */
    public bool Search(string word) {
        
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public bool StartsWith(string prefix) {
        
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.Insert(word);
 * bool param_2 = obj.Search(word);
 * bool param_3 = obj.StartsWith(prefix);
 */

TrieNode 클래스를 만들어줍니다.
두 변수를 가집니다.
word는 단어인지 확인해주는 변수고
childeren 딕셔너리는 자식 트라이 노드를 가지고 있기 위함입니다.

class TrieNode {
    var word = false
    var children = [Character: TrieNode]()
}

class Trie {
    let root = TrieNode()
    
    /** Inserts a word into the trie. */
    func insert(_ word: String) {
        var node = root
        for char in word {
            if node.children[char] == nil {
                node.children[char] = TrieNode()
            }
            node = node.children[char]!
        }
        node.word = true
    }
    
    /** Returns if the word is in the trie. */
    func search(_ word: String) -> Bool {
        if let node = find(word) {
            return node.word
        }
        return false
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    func startsWith(_ prefix: String) -> Bool {
        return find(prefix) != nil
    }
    
    func find(_ str: String) -> TrieNode? {
        var node = root
        for char in str {
            if node.children[char] == nil {
                return nil
            }
            node = node.children[char]!
        }
        return node
    }
}

먼저 루트를 만들어 줍니다.
문자열 시작이 다 다르기 때문에 문자열은 비워줍니다.

insert함수는 세로로 문자열을 넣어주는 함수입니다.
각 노드마다 하나의 문자를 가집니다.
그리고 마지막에 word를 true로 설정해 단어임을 표시해줍니다.

search함수는 단어가 트라이에 있는지 확인해주는 함수입니다.
단어를 찾으면 true를 리턴해주고 찾지 못하면 false를 리턴해줍니다.

startsWith함수는 prefix가 있는지 확인해주는 함수입니다.

find함수는 아래로 노드를 현재 노드를 움직이는 역할을 해줍니다.
주어진 문자열이 자식에 있는지 확인하고 있으면 다음 자식으로 이동하고 없으면 nil을 리턴해줍니다.

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