Interview Question |Construct a trie from scratch | Trie | C++

Interview Question |Construct a trie from scratch | Trie | C++

class TrieNode {
public:
    TrieNode *child[26];
    bool isWord;
    TrieNode() {
        isWord = false;
        for (auto &a : child) a = nullptr;
    }
};
class Trie {
    TrieNode* root;
public:
    Trie() {
        root = new TrieNode();
    }
    void insert(string s) {
        TrieNode *p = root;
        for (auto &a : s) {
            int i = a - 'a';
            if (!p->child[i]) p->child[i] = new TrieNode();
            p = p->child[i];
        }
        p->isWord = true;
    }
    bool search(string key, bool prefix=false) {
        TrieNode *p = root;
        for (auto &a : key) {
            int i = a - 'a';
            if (!p->child[i]) return false;
            p = p->child[i];
        }
        if (prefix==false) return p->isWord;
        return true;
    }
    bool startsWith(string prefix) {
        return search(prefix, true);
    }
};

English :

The TrieNode class represents a node in the trie. Each node has an array of 26 pointers to other nodes, one for each possible character. The isWord member variable indicates whether the node represents the end of a word.

The Trie class represents the entire trie data structure. It has a single member variable, root, which is a pointer to the root node of the trie.

The insert() method inserts a string into the trie. It starts at the root node and traverses the trie, following the characters in the string. If a node does not exist for a given character, a new node is created. Once the end of the string is reached, the isWord member variable of the current node is set to true.

The search() method searches for a string in the trie. It starts at the root node and traverses the trie, following the characters in the string. If a node does not exist for a given character, the search fails. If the end of the string is reached and the isWord member variable of the current node is set to true, the search succeeds. The prefix parameter indicates whether the search should match the entire string or only a prefix of the string.

The startsWith() method checks whether the trie contains a string that starts with a given prefix. It simply calls the search() method with the prefix parameter set to true.

Here is an example of how to use the Trie class:

Trie trie;

// Insert some strings into the trie.
trie.insert("hello");
trie.insert("world");

// Search for a string in the trie.
bool found = trie.search("hello");

// Check whether the trie contains a string that starts with a given prefix.
bool startsWith = trie.startsWith("he");

Hindi :

TrieNode वर्ग ट्राई में एक नोड का प्रतिनिधित्व करता है। प्रत्येक नोड में अन्य नोड्स के लिए 26 पॉइंटर्स की एक सरणी होती है, एक प्रत्येक संभावित वर्ण के लिए। isWord सदस्य चर इंगित करता है कि क्या नोड किसी शब्द के अंत का प्रतिनिधित्व करता है।

Trie वर्ग संपूर्ण ट्राई डेटा संरचना का प्रतिनिधित्व करता है। इसमें एक एकल सदस्य चर root है, जो ट्राई के रूट नोड का पॉइंटर है।

insert() मेथड ट्राई में एक स्ट्रिंग सम्मिलित करता है। यह रूट नोड से शुरू होता है और ट्राई को ट्रैवर्स करता है, स्ट्रिंग में वर्णों का अनुसरण करता है। यदि किसी दिए गए वर्ण के लिए कोई नोड मौजूद नहीं है, तो एक नया नोड बनाया जाता है। एक बार स्ट्रिंग का अंत पहुंचने पर, वर्तमान नोड के isWord सदस्य चर को true पर सेट किया जाता है।

search() मेथड ट्राई में एक स्ट्रिंग की खोज करता है। यह रूट नोड से शुरू होता है और ट्राई को ट्रैवर्स करता है, स्ट्रिंग में वर्णों का अनुसरण करता है। यदि किसी दिए गए वर्ण के लिए कोई नोड मौजूद नहीं है, तो खोज विफल हो जाती है। यदि स्ट्रिंग का अंत पहुंच जाता है और वर्तमान नोड का isWord सदस्य चर true पर सेट है, तो खोज सफल होती है। prefix पैरामीटर इंगित करता है कि क्या खोज को पूरी स्ट्रिंग से मेल खाना चाहिए या केवल स्ट्रिंग के उपसर्ग से।

startsWith() मेथड जांचता है कि क्या ट्राई में एक स्ट्रिंग शामिल है जो किसी दिए गए उपसर्ग से शुरू होती है। यह केवल search() मेथड को prefix पैरामीटर true पर सेट के साथ कॉल करता है।

Trie वर्ग का उपयोग करने का एक उदाहरण यहां दिया गया है:

Trie trie;

// Insert some strings into the trie.
trie.insert("hello");
trie.insert("world");

// Search for a string in the trie.
bool found = trie.search("hello");

// Check whether the trie contains a string that starts with a given prefix.
bool startsWith = trie.startsWith("he");

Hinglish :

TrieNode class ek node ko represent karta hai trie mein. Har node mein ek array hota hai 26 pointers ka, ek har possible character ke liye. isWord member variable yeh batata hai ki node kisi word ke end ko represent karta hai ki nahi.

Trie class puri trie data structure ko represent karta hai. Ismein ek hi member variable hota hai, root, jo trie ke root node ka pointer hota hai.

insert() method ek string ko trie mein insert karta hai. Yeh root node se start hota hai aur trie ko traverse karta hai, string ke characters ko follow karta hai. Agar kisi character ke liye node exist nahi karta hai, toh ek naya node create kiya jata hai. Jab string ke end tak pohoch jaate hain, toh current node ke isWord member variable ko true set kiya jata hai.

search() method trie mein ek string ko search karta hai. Yeh root node se start hota hai aur trie ko traverse karta hai, string ke characters ko follow karta hai. Agar kisi character ke liye node exist nahi karta hai, toh search fail ho jaati hai. Agar string ke end tak pohoch jaate hain aur current node ke isWord member variable ko true set kiya gaya hai, toh search successful hoti hai. prefix parameter yeh batata hai ki search ko puri string se match karna hai ya string ke ek prefix se.

startsWith() method yeh check karta hai ki trie mein kisi string ko contain karta hai ki nahi jo ek diye hue prefix se start hoti hai. Yeh simply search() method ko call karta hai prefix parameter ko true set karke.

Trie trie;

// Insert some strings into the trie.
trie.insert("hello");
trie.insert("world");

// Search for a string in the trie.
bool found = trie.search("hello");

// Check whether the trie contains a string that starts with a given prefix.
bool startsWith = trie.startsWith("he");