文字列のサブシーケンスは、文字の順序を変更せずに文字列の任意の位置 (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」に分割することはできません。したがって、答えは「いいえ」です。
次の 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」を返します。
このチュートリアルでは、指定された文字列がサブシーケンス ABC にのみ分割できるかどうかを確認するプログラムを実装しました。周波数を保存する必要があったため、ハッシュ法を実装しました。この方法では主に 3 つの条件をチェックします。すべての条件が満たされた場合、文字列を "ABC" の部分列にのみ分割できることを意味します。
以上が指定された文字列が ABC のサブシーケンスにのみ分割できるかどうかを確認しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
