技術共有

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

原题链接🔗：Trie (プレフィックスツリー) の実装
困難: 中⭐️⭐️

トピック

Trie (「トライ」のように発音) または プレフィックスツリー 文字列データセット内のキーを効率的に格納および取得するために使用されるツリー データ構造です。このデータ構造には、オートコンプリートやスペル チェックなど、非常に多くの使用例があります。

Trie クラスを実装してください。

• Trie() プレフィックス ツリー オブジェクトを初期化します。
• void insert(String word) 文字列をプレフィックス ツリーに挿入するword 。
• boolean search(String word) 文字列の場合word プレフィックス ツリーで、return true(つまり、取得前に挿入されている); それ以外の場合は戻ります。 false 。
• boolean startsWith(String prefix) 文字列が以前に挿入されている場合 word接頭辞の 1 つは、 prefix 、戻る true ; それ以外の場合は戻りますfalse。

例：

入力
[“Trie”、“挿入”、“検索”、“検索”、“startsWith”、“挿入”、“検索”]
[[]、[“アップル”]、[“アップル”]、[“アプリ”]、[“アプリ”]、[“アプリ”]、[“アプリ”]]
出力
[null、null、true、false、true、null、true]

説明する
トライ trie = new Trie();
trie.insert(“apple”);
trie.search("apple"); // True を返します。
trie.search("app"); // False を返します。
trie.startsWith("app"); // True を返します。
trie.insert(“アプリ”);
trie.search("app"); // True を返します。

ヒント：

• 1 <= 単語の長さ、接頭辞の長さ <= 2000
• 単語と接頭辞は英小文字のみで構成されています
• insert、search、startsWith 呼び出しの合計数が 3 * 10 を超えないこと⁴ 二流

プレフィックスツリー

トライ ツリー (「トライ」と発音) とも呼ばれるプレフィックス ツリーは、文字列のコレクションを格納するために使用されるデータ構造です。これにより、文字列の高速な取得と挿入、および文字列プレフィックスのクエリが可能になります。接頭辞ツリーの各ノードは文字列の接頭辞を表し、各ノードの子は 1 文字を追加する接頭辞の可能なすべての拡張を表します。

• プレフィックスツリーの特徴：
  • スペース効率: 多数の共通プレフィックスを含む文字列コレクションの場合、プレフィックス ツリーによりストレージ スペースを節約できます。
  • 時間効率: 挿入操作と検索操作の時間計算量は通常 O(m) です。ここで、m は文字列の長さです。
  • 動的コレクション: プレフィックス ツリーは文字列を動的に挿入および削除できるため、頻繁な更新が必要なシナリオに適しています。
• プレフィックスツリーの基本操作：
  • 入れる: ルート ノードから 1 文字ずつツリーに文字列を挿入します。その文字に対応する子ノードが存在しない場合は、新しいノードを作成します。
  • 検索: ルート ノードから 1 文字ずつツリー内に文字列が存在するかどうかを検索します。文字の子ノードが存在しない場合、検索は失敗します。
  • 前方一致検索: 検索操作と同様に、特定の文字列を先頭に持つ文字列があるかどうかを確認しますが、最後のノードの終了フラグを確認する必要はありません。
  • 消去: ツリーから文字列を削除するには、他の文字列の共通プレフィックス ノードが削除されないようにしながら、ノードを再帰的に削除する必要があります。
• プレフィックスツリーの適用シナリオ：
  • オートコンプリート: 検索エンジンまたはテキスト エディタで、ユーザーが入力した接頭辞に基づいて補完候補をすばやく提供します。
  • スペルチェック: ユーザーが入力した単語のスペルが正しいかどうかをチェックし、正しいスペルの提案を提供します。
  • IPルーティング: ネットワークでは、最長プレフィックス マッチングを使用してパケットのルーティング パスが決定されます。
  • 遺伝子配列解析: バイオインフォマティクスにおいて、遺伝子配列を迅速に照合して取得するために使用されます。

答え

1. 問題解決のアイデア：

Trie (プレフィックス ツリー) は、文字列データセット内のキーを高速に取得するために使用されるツリー データ構造です。これは、各ノードが文字を表し、ルートからノードへのパスが文字列を表す特別な種類のツリーです。 トライ ツリーは、自動補完やスペル チェックなどの機能を実装するためによく使用されます。

以下は、トライ ツリーを実装するための基本的な手順と問題解決のアイデアです。

1. Trie ノードの定義：

   • 各 Trie ノードには通常、単語の終わりを表す一連の文字またはブール値、および子ノードへのポインタが含まれています。

2. トライの初期化：

   • 文字を含まないが、すべての単語の開始点として機能するルート ノードを作成します。

3. 挿入操作：

   • ルート ノードから開始して、文字列内の各文字が挿入されるようになります。
     • キャラクターに対応する子ノードが存在しない場合は、新規に子ノードを作成します。
     • 現在のノードを対応する子ノードに移動します。

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. コードウェアハウスのアドレス：トライ