指定された文字列が ABC のサブシーケンスにのみ分割できるかどうかを確認します

文字列のサブシーケンスは、文字の順序を変更せずに文字列の任意の位置 (0 個以上の要素) から文字を取得できる文字列の一部です。新しい文字列。この問題では、文字列のすべての文字が「A」、「B」、または「C」文字のいずれかである長さ N の文字列が与えられます。私たちの仕事は、文字列がサブシーケンス「ABC」または「Not」にのみ分割できることを見つけることです。文字列がサブシーケンス「ABC」のみに分割されている場合は「yes」を返し、それ以外の場合は「no」を返します。

リーリー

手順 - 分割方法は、次のように文字列を「ABC」の 2 つの部分列に分割します。 -

• 考えられる方法の 1 つは、インデックス 0、2、および 3 の文字を取得してサブシーケンス "ABC" を形成し、次にインデックス 1、4、および 5 の文字を取得してサブシーケンス "ABC" を形成することです。 。

• もう 1 つの可能な方法は、インデックス 0、4、5 および 1、2、3 の文字を取得してサブシーケンス "ABC" を形成することです。

したがって、文字列は「ABC」の 2 つのサブシーケンスに分割できます。

リーリー

説明 - インデックス番号 5 にある「A」の場合、その後に「B」はありません。したがって、文字列全体を一意のサブシーケンス「ABC」に分割することはできません。したがって、答えは「いいえ」です。

方法 1: ハッシュマップを使用する

次の 2 つの観察結果があります -

• 文字列を「ABC」に分割する必要があり、文字「A」、「B」、および「C」の数が等しい必要があるため、文字列のサイズは 3 で割り切れる必要があります。そうしないと条件を満たせません。

• 文字「A」、「B」、「C」の頻度を数えるとき、「A」の数は「B」の数および「B」の数以上である必要があります。 " は 'C ' カウント以上である必要があります。 A のカウント >= B のカウント >= C のカウント

であるため

上記の観察に基づいて、確認する必要がある条件が 3 つあります。

• 予期される文字列サイズ % 3 == 0。

• は、A のカウント >= B のカウント >= C のカウントでなければなりません。

• 最後の条件は freq[ ‘A’ ] == freq[ ‘B’ ] == freq[ ‘C’ ] である必要があります。

指定された文字列「str」内の各文字の頻度を保存する必要があるため、ハッシュ マップを使用してこの問題を解決できます。

次の方法について段階的に説明します -

• まず、「checkSubsequences」という関数を作成します。この関数は、指定された文字列「str」をパラメータとして受け取り、可能であれば希望の文字列「yes」を返します。それ以外の場合は、戻り値として「no」を返します。 。

• 関数のすべての手順は次のとおりです-

• 文字列の長さを格納する変数「len」を作成します。

• 最初の条件を確認し、長さが 3 で割り切れない場合は「no」を返します。

• 文字「A」、「B」、「C」の頻度を保存するハッシュ マップを作成します。したがって、空間の複雑さは一定です。

• for ループを使用して、文字列を 0 から len 未満まで走査します。

  • 文字列の現在の文字数を増やします

  • 2 番目の条件を確認し、「A」のカウントが「B」のカウントより小さい場合、または「B」のカウントが「C」のカウントより小さい場合は、「No」を返します。

    li>

• for ループの後、最後の 3 番目の条件をチェックし、A のカウントが B のカウントと等しくない場合、または B のカウントが C のカウントと等しくない場合は、「いいえ」を返す必要があります。

• 最後に、すべての条件が満たされたら、「yes」を返します。

＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

時間と空間の複雑さ

文字列をトラバースするため、上記のコードの時間計算量は O(N) です。ここで、N は文字列のサイズです。

サイズが定数 3 である数値の頻度を保存しているため、上記のコードの空間計算量は O(1) です。

＃＃＃結論は＃＃＃

このチュートリアルでは、指定された文字列がサブシーケンス ABC にのみ分割できるかどうかを確認するプログラムを実装しました。周波数を保存する必要があったため、ハッシュ法を実装しました。この方法では主に 3 つの条件をチェックします。すべての条件が満たされた場合、文字列を "ABC" の部分列にのみ分割できることを意味します。

以上が指定された文字列が ABC のサブシーケンスにのみ分割できるかどうかを確認しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。