[Tree] Trie 활용 문제들

인터뷰에 나올법한 좋은 문제.

Trie를 이용해서 풀 수도 있는데, 바로 'find' 함수 한번만 써서는 못 풀 것 같다.

 

(주어진 prefix를 가지는 단어 3개까지 출력해야 하므로)

Trie 구조를 조금 수정해서 각 노드마다 'recommendation'을 만들자.

거기에 해당 prefix를 가지는 단어를 3개까지 저장하도록 한다면?

find 해서 prefix가 찾아질 때, recommendation을 그대로 반환하면 됨.

 

https://leetcode.com/problems/search-suggestions-system/discuss/436151/JavaPython-3-Simple-Trie-and-Binary-Search-codes-w-comment-and-brief-analysis.

[Java/Python 3] Simple Trie and Binary Search codes w/ comment and brief analysis. - LeetCode Discuss

 

 

---

구현한 Trie 모음

 

C++ 재귀 Trie - Pointer와 char* 사용해서 구현

constexpr int MAX_LEN = 26; // For example) alphabet 26 letters
struct Trie {
    Trie* child[MAX_LEN]; // child 노드의 포인터 저장 (initially 'nullptr')
    bool isEnd; // 현재 트라이 노드에서 끝나는 문자열이 있는가
    bool hasChild; // 하위 트라이 노드가 더 있는가 (= 더 긴 문자열 존재)

    // Constructor
    Trie() :isEnd(false), hasChild(false) {
        fill(child, child + MAX_LEN, nullptr);
    }
    // Destructor
    ~Trie() {
        for (int i = 0; i < MAX_LEN; i++) {
            if (child[i])
                delete child[i];
        }
    }
    // 문자열 key를 현재 노드부터 삽입
    void insert(const char* key) {
        // 문자열의 끝 
        if (*key == '\0') isEnd = true;
        else {
            int next = *key - 'a';
            if (!child[next]) child[next] = new Trie; // 처음 추가되는 문자인 경우 노드 생성
            hasChild = true;
            child[next]->insert(key + 1);
        }
    }
    // 문자열 key가 트라이 내에 있는지 체크
    bool find(const char* key) {
        // 문자열의 끝; 현재 트라이 노드에서 끝나는 문자열이 있는지 체크
        if (*key == '\0') return isEnd;
        else {
            int next = *key - 'a';
            if (!child[next]) return false; // 다음 문자가 트라이에 저장되어있지 않음 = key가 없다는 뜻
            else return child[next]->find(key + 1);
        }
    }
    // 문자열 key를 Prefix로 가지는 다른 문자열이 트라이 내에 있는지 체크
    bool usedAsPrefix(const char* key) {
        if (*key == '\0') return hasChild;
        else {
            int next = *key - 'a';
            if (!child[next]) return false;
            else return child[next]->usedAsPrefix(key + 1);
        }
    }
};

 

C++ Iterative Trie - vector, string 사용하고 좀 더 직관적으로 함수 바꿈

constexpr int MAX_LEN = 26; // For example) alphabet 26 letters
struct Trie {
    vector<Trie*> child; // child 노드의 포인터 저장 (initially 'nullptr')
    
    // Constructor
    Trie() {
        child = vector<Trie*>(MAX_LEN, nullptr);
    }
    // Destructor
    ~Trie() {
        for (int i = 0; i < MAX_LEN; i++) {
            if (child[i])
                delete child[i];
        }
    }
};


void insert(string key, Trie* root) {
    Trie* node = root;
    for (char c : key) {
        Trie*& next = node->child[c - 'a'];
        if (!next) next = new Trie;
        node = next;
    }
}

bool find(string key, Trie* root) {
    Trie* node = root;
    FOR(i, 0, key.size()){
        char c = key[i];
        Trie*& next = node->child[c - 'a'];
        if (!next) return false;
        node = next;
    }
    return true;

    /*
    // Child가 있는지 확인 - 해당 key를 prefix로 가지는 단어가 있는지 체크
    for (Trie* n : node->child)
        if (!n) return true;
    return false;
    */
}

int main() {
#ifdef DBG
	freopen("../input.txt", "r", stdin);
#endif  
    
    Trie* root = new Trie;
    insert("hello", root);
    insert("my", root);
    insert("name", root);
    insert("is", root);

    // 1. 문자열이 Trie에 있는지 find (저장된 문자열 검색)
    cout << find("hello", root) << " " << find("wrong", root) << "\n"; // 1 0

    // 2. 문자열을 Prefix로 가지는 문자열이 있는지 체크
    // -> Find 조금 수정해서 체크 가능

    delete root;
    return 0;
}

 

Python Iterative Trie - dict 사용; 저장 데이터의 type이 섞여도 Ok (lower + upper case + number str)

class Trie:
    def __init__(self):
        self.child = {}

def insert(key: str, root: Trie) -> None:
    node = root
    for char in key:
        if char not in node.child:
            node.child[char] = Trie()
        node = node.child[char]

def find(key: str, root: Trie) -> bool:    
    node = root          
    for char in key:
        if node:
            node = node.child.get(char, None)
        else:
            return False
    return True
    # Found key in the Trie


# Testing
root = Trie()
words = ["Hello", "my", "name", "is", "James"]
for s in words:
    insert(s, root)

print(find("Hello", root), find("hello", root))
print(find("James", root), find("james", root))
print(find("1234", root))