1. 概要

このチュートリアルでは、文字列の個別のサブシーケンスの数を見つける問題について説明します。

まず、問題を定義し、それを説明するための例を示します。 次に、この問題を解決するための2つの異なるアプローチを紹介し、それらの実装と空間および時間の複雑さを処理します。

2. 問題の定義

文字列があり、その中にある個別のサブシーケンスの数を数えるように求められたとします。

文字列のサブシーケンスは、残りの要素の順序を変更せずに0個以上の要素を削除することにより、指定された文字列から派生できるシーケンスであることを思い出してください。

次の例を見てみましょう。

文字列が与えられたら、その文字列のすべての個別のサブシーケンスを取得しましょう（赤い四角は選択された文字を表します）：

ご覧のとおり、指定された文字列にはさまざまなサブシーケンスがあります。

3. 素朴なアプローチ

3.1. 本旨

このアプローチの主なアイデアは、指定された文字列のすべての可能なサブシーケンスを生成することです。 次に、それらを set に入れて、重複を取り除きます。 最終的に、そのセットのサイズは、私たちが持っている個別のサブシーケンスの数に等しくなります。

最初に、指定された文字列のすべての可能なサブシーケンスを生成するbacktrackingメソッドがあります。 次に、指定された文字列の各文字について、現在のサブシーケンスで選択するか、そのままにします。 次に、文字列の最後に到達すると、1つの潜在的なサブシーケンスがあります。 したがって、さまざまなサブシーケンスを格納するセットに追加します。

最後に、指定された文字列の個別のサブシーケンスの数は、セットのサイズに等しくなります。

3.2. アルゴリズム

アルゴリズムの実装を見てみましょう。

最初に、指定された文字列のすべての可能なサブシーケンスを生成する関数を宣言します。 関数には4つのパラメーターがあります。 は文字列自体であり、指定された文字列内の現在の位置を表します。 これまでの現在のサブシーケンスを表し、指定された文字列から生成できる可能性のあるすべての個別のサブシーケンスを表します。

まず、バックトラック関数の基本ケースは、文字列の最後に到達したときです。次に、必要な電流を追加します。 次に、キャラクターごとに2つの選択肢があります。

  1. 選択：現在の文字をに追加し、次の文字に移動します。 その再帰呼び出しから戻ったら、文字の追加に戻り、の最後の文字をポップします。
  2. 残す：現在の文字を無視して、次の文字に移動します。

最後に、のサイズは、指定された文字列の個別のサブシーケンスの数に等しくなります。

3.3. 複雑さ

このアルゴリズムの時間計算量はです。ここで、は指定された文字列の長さです。 その理由は、文字列の文字ごとに、選択するか残すかの2つのオプションがあるためです。

一方、このアルゴリズムのスペースの複雑さはです。ここで、は、指定された文字列のすべての可能なサブシーケンスの長さの合計です。 この複雑さの背後にある理由は、可能なサブシーケンスごとに、それをに格納するためです。

4. 動的計画法アプローチ

4.1. 本旨

このアプローチの主なアイデアは、文字列の個別のサブシーケンスの数を、それらのサブシーケンスを生成せずにカウントする式について考えることです。

最初に、それが、指定された文字列の最初の文字から生成される可能性のある個別のサブシーケンスの数を表すとしましょう。 を計算するには、指定された文字列の文字ごとに2つのオプションがあるため、を掛けます。それを選択するか、残すかです。 次に、現在の文字を追加するときに生成される可能性のある重複するサブシーケンスの数を減算します。 したがって、前のアイデアを次の式で表すことができます。

   

問題は、重複の数を見つけることです。 現在の文字をサブシーケンスに追加すると、2つの重複ケースがあります。

  1. この文字が指定された文字列に初めて表示される場合、前にこの文字で終わるサブシーケンスはありません。 したがって、重複の数はゼロです。
  2. この文字が前に表示されている場合、重複の数は、この文字が最後に出現したときに終了するすべてのサブシーケンスの数と等しくなります。 正式には、が前への最後の出現のインデックスである場合、文字の追加による重複の数はです。

この問題には重複する状態があるため、動的計画法を使用して解決します。

最後に、は、指定された文字列の個別のサブシーケンスの数を表します。

4.2. アルゴリズム

アルゴリズムの実装を見てみましょう。

最初に、文字列の個別のサブシーケンスの数を返す関数があります。 指定された文字列を表す1つのパラメータがあります。

最初に、配列を宣言します。これにより、特定の位置までの個別の文字列サブシーケンスの数が格納されます。 また、特定の文字が最後に出現したときの位置を格納する配列を宣言します。 最初は、その値はすべてに等しくなります。

次に、の値をに設定します。これは、空のサブシーケンスを表します。 次に、キャラクターごとに2つのオプションがあります。 それを選ぶか、残すかのどちらかです。 したがって、前の位置の答えに。を掛けます。 次に、現在のキャラクターが以前に発生したかどうかを確認します。 もしそうなら、現在の答えからその位置の答えを引きます。 その後、の値を現在の位置と等しくなるように更新します。

最後に、には、指定された文字列の個別のサブシーケンスの数が含まれます。

4.3. 複雑

このアルゴリズムの時間計算量はです。ここで、は指定された文字列の長さです。 この複雑さの背後にある理由は、各文字を1回だけ反復するためです。

このアルゴリズムのスペースの複雑さはです。ここで、は指定された文字列の長さであり、はアルファベットのサイズです。 その理由は、指定された文字列の位置ごとに回答を保存し、可能な文字ごとに、最後に表示されたときのインデックスを保存するためです。

5. 結論

この記事では、特定の文字列内の個別のサブシーケンスの数を見つける問題について説明しました。 まず、問題を説明する例を示しました。 次に、それを解決するための2つの異なるアプローチを検討しました。2番目のアプローチの方が時間とスペースの複雑さが優れていました。

最後に、それらの実装をウォークスルーし、それぞれの背後にある考え方を説明しました。