テクニカル記事

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

Trie クラスを実装します。

Trie() トライオブジェクトを初期化します。
void insert(String word) 文字列 word をトライに挿入します。
int countWordsEqualTo(String word) トライ内の文字列 word のインスタンスの数を返します。
int countWordsStartingWith(String prefix) 文字列プレフィックスをプレフィックスとして持つトライ内の文字列の数を返します。
void erasing(String word) トライから文字列 word を消去します。

'('、')'、'{'、'}'、'['、']' の文字のみを含む文字列が与えられた場合、入力文字列が有効かどうかを判断します。

入力文字列は次の場合に有効です。

開いた括弧は同じ種類の括弧で閉じる必要があります。
開いた括弧は正しい順序で閉じる必要があります。
すべての閉じ括弧には、同じタイプの対応する開き括弧があります。

mxn の文字のボードと単語の文字列のリストが与えられた場合、ボード上のすべての単語を返します。

各単語は、水平または垂直に隣接するセルの文字から構成する必要があります。 同じ文字セルを 1 つの単語内で複数回使用することはできません。

新しい単語の追加と、文字列が以前に追加された文字列と一致するかどうかの検索をサポートするデータ構造を設計します。

WordDictionary クラスを実装します。

WordDictionary() オブジェクトを初期化します。
void addWord(word) データ構造に単語を追加します。これは後で照合できます。
bool search(word) データ構造内に word に一致する文字列がある場合は true を返し、それ以外の場合は false を返します。単語にはドット「.」が含まれる場合があります。ドットは任意の文字と一致できます。

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

Trie クラスを実装します。

Trie() トライオブジェクトを初期化します。
void insert(String word) 文字列 word をトライに挿入します。
boolean search(String word) 文字列 word がトライ内にある場合 (つまり、以前に挿入されていた場合) は true を返し、それ以外の場合は false を返します。
boolean startsWith(String prefix) 接頭辞 prefix を持つ以前に挿入された文字列単語がある場合は true を返し、それ以外の場合は false を返します。

バイナリ検索ツリー (BST) が与えられた場合、BST 内の 2 つの指定されたノードの最下位共通祖先 (LCA) ノードを検索します。

Wikipedia の LCA の定義によると、「最低共通祖先は、2 つのノード p と q の間で、p と q の両方を子孫として持つ T 内の最低のノードとして定義されます (ノードがそれ自身の子孫になることを許可します)。」

二分探索木のルートと整数 k が与えられると、木内のすべてのノードの値のうち k 番目に小さい値 (1 から始まるインデックス) を返します。

バイナリ ツリーのルートが与えられた場合、それが有効なバイナリ サーチ ツリー (BST) であるかどうかを判断します。

有効な BST は次のように定義されます。

ノードの左のサブツリーには、ノードのキーよりも小さいキーを持つノードのみが含まれます。
ノードの右サブツリーには、ノードのキーよりも大きいキーを持つノードのみが含まれます。
左と右のサブツリーも両方ともバイナリ検索ツリーである必要があります。