प्रौद्योगिकी साझेदारी

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

原题链接🔗：Trie (उपसर्गवृक्षः) इति कार्यान्वयनम् ।
कठिनता: मध्यम⭐️⭐️

विषय

त्र्ये ("प्रयत्न" इव उच्चारितः) वा उपसर्गवृक्षः स्ट्रिंग् डाटासेट् मध्ये कुञ्जीनां कुशलतापूर्वकं संग्रहणं पुनः प्राप्तुं च उपयुज्यते इति वृक्षदत्तांशसंरचना अस्ति । अस्मिन् दत्तांशसंरचनायाः कानिचन उपयोगप्रकरणाः सन्ति, यथा स्वयमेव समाप्तिः, वर्तनीपरीक्षा च ।

कृपया Trie वर्गं कार्यान्वितं कुर्वन्तु:

• Trie() उपसर्गवृक्षवस्तुं आरभत ।
• void insert(String word) उपसर्गवृक्षे स्ट्रिंग् निवेशयन्तुword 。
• boolean search(String word) यदि स्ट्रिंग्word उपसर्गवृक्षे प्रत्यागच्छतु true(अर्थात् पुनः प्राप्तेः पूर्वं सम्मिलितः अस्ति); false 。
• boolean startsWith(String prefix) यदि पूर्वं तारं प्रविष्टा अस्ति wordउपसर्गेषु एकः prefix ,निर्वतनम् true ;false。

उदाहरण:

प्रवेश
[“प्रयत्नय”, “प्रवेश”, “अन्वेषण”, “अन्वेषण”, “प्रारम्भः”, “प्रवेश”, “अन्वेषण”] ।
[[], [“सेब”], [“सेब”], [“एप्”], [“एप्”], [“एप्”], [“एप्प”]] ।
उत्पादनम्
[शून्य, शून्य, सत्य, मिथ्या, सत्य, शून्य, सत्य]

व्याख्याति
Trie trie = नया Trie ();
trie.insert (“सेब”);
trie.search ("apple"); // सत्यं प्रत्यागच्छतु
trie.search ("अनुप्रयोग"); // गलत रिटर्न
trie.startsWith ("अनुप्रयोग"); // सत्यं प्रत्यागच्छतु
trie.insert (“अनुप्रयोग”);
trie.search ("app"); // सत्यं प्रत्यागच्छतु

संकेत:

• १ <= शब्द.दीर्घता, उपसर्ग.दीर्घता <= २०००
• शब्दः उपसर्गः च केवलं लघु-आङ्ग्ल-अक्षरैः युक्तौ भवतः
• insert, search, startsWith इति आह्वानस्य कुलसंख्या 3 * 10 इत्यस्मात् अधिका न भवति⁴ द्वितीय-श्रेणी

उपसर्गवृक्षः

उपसर्गवृक्षः, यः Trie वृक्षः (उच्चारणः "try") इति अपि ज्ञायते, सः एकः दत्तांशसंरचना अस्ति यस्य उपयोगः तारसङ्ग्रहस्य संग्रहणार्थं भवति, यत् तारानाम् शीघ्रं पुनः प्राप्तिः, निवेशनं च, तथैव स्ट्रिंग् उपसर्गाणां प्रश्नान् च अनुमन्यते उपसर्गवृक्षस्य प्रत्येकं नोड् स्ट्रिंग् इत्यस्य उपसर्गं प्रतिनिधियति, प्रत्येकस्य नोड् इत्यस्य बालकाः च उपसर्गस्य सर्वान् सम्भाव्यविस्तारान् प्रतिनिधियन्ति ये एकं वर्णं योजयन्ति ।

• उपसर्गवृक्षाणां लक्षणम्：
  • अन्तरिक्षदक्षता: बहूनां सामान्यउपसर्गयुक्तानां स्ट्रिंग्-सङ्ग्रहानां कृते उपसर्गवृक्षाः भण्डारणस्थानं रक्षितुं शक्नुवन्ति ।
  • कालदक्षता: सम्मिलनस्य अन्वेषणक्रियाणां च समयजटिलता प्रायः O(m) भवति, यत्र m स्ट्रिंग् इत्यस्य दीर्घता भवति ।
  • गतिशील संग्रह: उपसर्गवृक्षः गतिशीलरूपेण ताराः सम्मिलितुं विलोपयितुं च शक्नोति, यत् नित्यं अद्यतनीकरणस्य आवश्यकतां विद्यमानानाम् परिदृश्यानां कृते उपयुक्तम् अस्ति ।
• उपसर्गवृक्षाणां मूलभूतक्रियाः：
  • युज्: वृक्षे एकं स्ट्रिंग् सम्मिलितं कुर्वन्तु, मूलनोड्तः आरभ्य वर्णेन वर्णेन अधः गत्वा यदि वर्णस्य अनुरूपः बालनोड् नास्ति तर्हि नूतनं नोड् रचयन्तु ।
  • अन्वेषण: वृक्षे स्ट्रिंग् अस्ति वा इति अन्वेषणं कुर्वन्तु, मूलनोड्तः आरभ्य वर्णेन वर्णेन अधः गत्वा यदि कस्यचित् वर्णस्य बालनोड् नास्ति तर्हि अन्वेषणं विफलं भवति ।
  • उपसर्गः अन्वेषणम्: अन्वेषणक्रियायाः सदृशं, कस्यचित् स्ट्रिंग् इत्यस्य उपसर्गं किमपि स्ट्रिंग् अस्ति वा इति परीक्षते, परन्तु अन्तिमस्य नोड् इत्यस्य अन्त्यध्वजस्य जाँचस्य आवश्यकता नास्ति ।
  • लुप्: वृक्षात् स्ट्रिंग् विलोपयितुं अन्येषां स्ट्रिंग्-सामान्य-उपसर्ग-नोड्स् न विलोप्यन्ते इति सुनिश्चित्य नोड्स् पुनरावर्तनीयरूपेण विलोपयितुं आवश्यकम् अस्ति ।
• उपसर्गवृक्षस्य अनुप्रयोगपरिदृश्यानि：
  • स्वतः सम्पन्न: अन्वेषणयन्त्रेषु अथवा पाठसम्पादकेषु उपयोक्त्रा प्रविष्टानां उपसर्गानाम् आधारेण शीघ्रं समाप्तिसूचनानि प्रदातव्यानि।
  • वर्तनीपरीक्षा: उपयोक्त्रा प्रविष्टः शब्दः सम्यक् वर्तनी अस्ति वा इति परीक्षते तथा च सम्यक् वर्तनीसूचनाः प्रदाति।
  • IP मार्गनिर्धारणम्: जालपुटे दीर्घतमस्य उपसर्गमेलनस्य उपयोगः पैकेट् इत्यस्य मार्गमार्गं निर्धारयितुं भवति ।
  • जीन अनुक्रम विश्लेषण: जैवसूचनाशास्त्रे जीनक्रमस्य शीघ्रं मेलनं कर्तुं पुनः प्राप्तुं च उपयुज्यते ।

उत्तरम्‌

1. समस्यानिराकरणविचाराः：

Trie (उपसर्गवृक्षः) इति वृक्षदत्तांशसंरचना यस्य उपयोगः स्ट्रिंग्दत्तांशसमूहे कीलानां द्रुतपुनर्प्राप्त्यर्थं भवति । एषः विशेषः प्रकारः वृक्षः यस्मिन् प्रत्येकं नोड् एकं वर्णं प्रतिनिधियति, मूलतः नोड्पर्यन्तं मार्गः च तारं प्रतिनिधियति । स्वचालितसमाप्तिः, वर्तनीपरीक्षणम् इत्यादीनि कार्याणि कार्यान्वितुं प्रायः Trie वृक्षाणां उपयोगः भवति ।

Trie वृक्षस्य कार्यान्वयनार्थं मूलभूतपदार्थाः समस्यानिराकरणविचाराः च निम्नलिखितरूपेण सन्ति ।

1. Trie नोड्स परिभाषयन्तु：

   • प्रत्येकं Trie नोड् मध्ये प्रायः शब्दस्य अन्तं प्रतिनिधितुं वर्णानाम् समुच्चयः अथवा Boolean मूल्यं भवति, बालनोड् इत्यस्य सूचकाः च भवन्ति ।

2. Trie इत्यस्य आरम्भं कुर्वन्तु：

   • एकं मूलनोड् रचयन्तु यस्मिन् वर्णाः नास्ति परन्तु सर्वेषां शब्दानां आरम्भबिन्दुरूपेण कार्यं करोति ।

3. insert operation：

   • मूलनोड्तः आरभ्य, निवेशनीयस्य स्ट्रिंग् मध्ये प्रत्येकं वर्णस्य कृते:
     • यदि वर्णस्य अनुरूपं बालनोड् नास्ति तर्हि नूतनं बालनोड् रचयन्तु ।
     • वर्तमान नोड् तत्सम्बद्धं बाल नोड् प्रति चालयन्तु ।

4. अन्वेषण संचालन：

   • मूलनोड् तः आरभ्य, भवन्तः अन्वेष्टुम् इच्छन्ति स्ट्रिंग् मध्ये प्रत्येकस्य वर्णस्य कृते:
     • यदि वर्णस्य अनुरूपः बालनोड् अस्ति तर्हि अन्वेषणं कुर्वन्तु ।
     • यदि नास्ति तर्हि अन्वेषणविफलता प्रत्यागच्छति ।

5. उपसर्गः अन्वेषणम्：

   • अन्वेषणक्रियायाः सदृशं, परन्तु केवलं स्ट्रिंग् इत्यस्य उपसर्गः अस्ति वा इति चिन्तयति ।

6. विलोपन संचालन(वैकल्पिक):

   • आवश्यकतानुसारं शब्दान् विलोपयितुं क्षमताम् कार्यान्वयन्तु, यस्मिन् सामान्यतया नोड्-विलोपनं भवति, तथा च नोड्-सन्दर्भगणनायाः निबन्धनस्य आवश्यकता भवति ।

7. स्वतः सम्पन्न कार्य(वैकल्पिक):

   • उपसर्गं दत्तं, तस्मात् उपसर्गात् आरभ्य सर्वाणि स्ट्रिंग् प्रत्यागच्छतु ।

2. c++ डेमो：

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;

    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

public:
    Trie() : children(26), isEnd(false) {}

    void insert(string word) {
        Trie* node = this;
        for (char ch : word) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr;
    }
};


int main() {
    Trie trie;
    trie.insert("apple");
    std::cout << trie.search("apple") << std::endl;   // 返回 1
    std::cout << trie.search("app") << std::endl;     // 返回 0
    std::cout << trie.startsWith("app") << std::endl; // 返回 1

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

• आउटपुट् परिणामः : १.

1
0
1

3. कोड गोदाम पता：त्रिये