Add and Search Word - Data Structure Design in C++ (Trie + Wildcard Search)

ออกแบบ Data Structure รองรับ 2 Operation:

• addWord(word)
• search(word)

search(word) ค้นหาคำตรงตัว หรือ Regular Expression ที่มีแค่ a-z และ . (Dot = ตัวอักษรอะไรก็ได้ 1 ตัว) เช่น เพิ่ม "bad", "dad", "mad" แล้ว search("pad")→false, search("bad")→true, search(".ad")→true, search("b..")→true

วิธีแก้

• สร้าง insertNode(head, s): ใช้ Trie (Prefix Tree) เก็บคำ
• curr := head, n := length of s
• for i = 0 to n-1: x := s[i], ถ้า child[x] ว่าง สร้างโหนดใหม่, curr := child[x]
• set isEnd of curr = true
• จาก addWord() เรียก insertNode()
• สร้าง check(curr, s, index): recursive search รองรับ wildcard '.' โดยลองทุกตัวอักษร a-z
• จาก search() เรียก check(head, word, 0)

ตัวอย่างโค้ด (C++)

#include <bits/stdc++.h>
using namespace std;

struct Node {
    bool isEnd;
    map child;
    Node() { isEnd = false; }
};

class WordDictionary {
public:
    Node* head;
    WordDictionary() { head = new Node(); }
    
    void insertNode(Node* head, string s) {
        Node* curr = head;
        int n = s.size();
        for(int i = 0; i < n; i++) {
            char x = s[i];
            if(!curr->child[x])
                curr->child[x] = new Node();
            curr = curr->child[x];
        }
        curr->isEnd = true;
    }
    
    void addWord(string word) { insertNode(head, word); }
    
    bool check(Node* curr, string s, int idx = 0) {
        if(idx == s.size()) return curr->isEnd;
        if(s[idx] == '.') {
            for(int i = 0; i < 26; i++) {
                char x = 'a' + i;
                if(curr->child[x] && check(curr->child[x], s, idx + 1))
                    return true;
            }
        } else {
            char x = s[idx];
            if(curr->child[x] && check(curr->child[x], s, idx + 1))
                return true;
        }
        return false;
    }
    
    bool search(string word) {
        Node* curr = head;
        return check(curr, word);
    }
};

main() {
    WordDictionary ob;
    ob.addWord("bad");
    ob.addWord("dad");
    ob.addWord("mad");
    cout << (ob.search("pad")) << endl;
    cout << (ob.search("bad")) << endl;
    cout << (ob.search(".ad")) << endl;
    cout << (ob.search("b..")) << endl;
}

Input

Initialize WordDictionary, call addWord() and search() in main()

Output

0 1 1 1