Thêm và Tìm kiếm Từ - Thiết kế cấu trúc dữ liệu C++ (Add and Search Word)

Giả sử phải thiết kế cấu trúc dữ liệu hỗ trợ hai thao tác:

• addWord(word)
• search(word)

search(word) có thể tìm từ chính xác hoặc biểu thức chính quy chỉ chứa chữ a-z hoặc dấu chấm (.). Dấu chấm đại diện cho bất kỳ chữ cái nào. Ví dụ: thêm "bad", "dad", "mad", thì search("pad") → false, search("bad") → true, search(".ad") → true, search("b..") → true.

Giải pháp dùng Trie (cây tiền tố):

• Định nghĩa insertNode(head, s): chèn từ vào Trie.
• Từ addWord(), gọi insertNode().
• Định nghĩa check(curr, s, index): đệ quy tìm kiếm, xử lý ký tự '.' bằng cách thử tất cả 26 chữ cái.
• Từ search(), gọi check(head, word, 0).

Ví dụ (C++)

#include 
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;
}

Đầu vào

Khởi tạo WordDictionary, gọi addWord() và search() như trong main()

Đầu ra

0 1 1 1