小文字と大文字が同じ数の部分文字列の数

この問題では、特定の文字列内に同じ数の小文字と大文字が含まれる文字列の総数をカウントする必要があります。この問題を解決する単純な方法は、すべての部分文字列を検索し、同じ数の小文字と大文字を持つ部分文字列の総数をカウントすることです。

効果的な方法は、部分配列の合計問題を使用することです。小文字を -1 として扱い、大文字を 1 として扱うことができ、問題を解決する両方の方法を学習します。

問題ステートメント- 小文字と大文字のアルファベットを含む文字列 str が与えられています。同じ数の小文字と大文字を含む部分文字列の合計数をカウントする必要があります。

＃＃＃例＃＃＃

入力

– str = 'TutOR'

出力

– 4

説明

– 同じ数の小文字と大文字を含む、「Tu」、「TutO」、「tO」、「utOR」の 4 つの部分文字列を取得できます

入力

– str = 'abcd'

出力

– 0

説明

– 文字列には小文字のみが含まれているため、同じ小文字と大文字を含む部分文字列を取得できません。 入力

– str = 'XYz'

出力

– 1

説明

- 「Yz」部分文字列のみを取得できます。

方法1

これは問題を解決するための素朴な方法です。 3 つのネストされたループを使用して、指定された文字列のすべての部分文字列を検索します。各部分文字列に同じ数の小文字と大文字が含まれているかどうかを確認します。そうであれば、カウントを 1 ずつ増やします。

＃＃＃アルゴリズム＃＃＃

変数「cnt」を定義し、ゼロに初期化します。

• for ループを使用して文字列を走査します
• ループ内で、「upperCase」変数と「 lowerCase 」変数を定義し、ゼロで初期化します

• コードに別のネ​​ストされたループを追加して、i 番目のインデックスから文字列を反復します。このようにして、i 番目のインデックスから j 番目のインデックスまでの部分文字列
  を取得できます。
• ネストされたループで、文字が大文字の場合、大文字の変数の値を 1 増やします。それ以外の場合は、小文字の変数の値を 1 ずつ増やします。

• 変数「upperCase」と「 lowerCase」の値が等しい場合は、「cnt」の値を 1 増やします。

• 「cnt」の値を返します。

• Example

  の中国語訳は次のとおりです:

  Example
リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量 - O(N^2)。ネストされたループを使用してすべての部分文字列を検索するためです。

一定空間を使用するため、空間複雑度 - O(1)。

方法 2

このメソッドでは、上記のメソッドのコードを最適化して、解の時間計算量を改善します。大文字は 1、小文字は -1 として扱われます。さらに、マップ データ構造を使用してプレフィックス合計の頻度を保存します。プレフィックスの合計がゼロ、またはマップに格納されているプレフィックスの合計と同じであることが判明した場合は、カウント値をインクリメントできます。

＃＃＃アルゴリズム＃＃＃

整数をキーと値のペアとして含む「合計」マップを定義します。

変数 'c​​nt' は、小文字と大文字が等しい部分文字列の総数を格納するために定義され、ゼロに初期化されます。同時に、プレフィックスと

を保存する変数「current」を定義します。

• 文字列のトラバースを開始します。現在の文字が大文字の場合は、「current」変数を 1 つ増やします。それ以外の場合は、「現在の」文字を 1 ずつ減らします。

• 'current' の値が 0 の場合、部分文字列を見つけて、'cnt' の値を 1
  だけインクリメントします。
• マップにキーとして「current」が含まれているかどうかを確認します。存在する場合は、その値を取得して「cnt」変数に追加します。

• マップ内の「現在の」キーの値を 1 増やします。

• Example

  の中国語訳は次のとおりです:

  Example
• 問題をより深く理解するため。入力例「TutOR」をデバッグしてみましょう。
  したがって、文字列の反復を開始すると、「current」の値は最初のインデックスで 0 になります。そこで、「cnt」の値を1増やします。繰り返しますが、3 番目のインデックスではゼロになります。そこで、「cnt」の値を1〜2増やします。以前に 0 を取得したので、それはマップ内に存在し、その値を「cnt」に追加する必要があります。そうすると、３になります。

4 番目のインデックスに到達すると、「current」変数の値は 1 になり、0 番目のインデックスで取得したのと同じように再び取得します。したがって、「cnt」に「1」を追加します。

基本的なロジックは、「current」が 0 の場合、部分文字列を取得するというものです。 「current」の値を再度取得すると、「current - current」がゼロであるため、2 つのインデックス間の文字列を取得できます。

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

時間計算量

- O(N)、文字列を 1 回しか走査しないため。

空間複雑度

– マップを使用してプレフィックスの合計を保存するため、O(N)。最悪の場合、文字列にすべて小文字または大文字が含まれる場合、O(N) 個のスペースが必要になります。

私たちは、上記の問題を解決するために 2 つの異なる方法を使用することを学びました。最初の方法は、ネストされたループを使用してすべての文字列をチェックします。一方、2 番目の方法は、時間の計算量の点で最初の方法よりも効率的ですが、より多くのスペースを消費します。

以上が小文字と大文字が同じ数の部分文字列の数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。