正確に X 個の母音を含む長さ K の部分文字列の数

この問題では、ちょうど K 個の母音を含む長さ K の部分文字列の総数を見つける必要があります。問題を解決する 2 つの異なる方法を見ていきます。簡単な方法を使用して、長さ K の各部分文字列内の母音の数を確認できます。さらに、この問題を解決するためにスライディング ウィンドウ アプローチを使用することもできます。

問題文 - 小文字と大文字のアルファベットを含む、長さ N の文字列 str が与えられます。正確に X 個の母音を含む長さ K の部分文字列の総数を数える必要があります。

＃＃＃例＃＃＃

入力

– str = "チュートリアルポイント"、K = 3、X = 2

出力

– 6

説明

– ちょうど 2 つの母音を含む長さ 3 の部分文字列は、「uto」、「ori」、「ria」、「ial」、「Poi」、「oin」です。 p>入力

– str = 'aeiou'、K = 2、X = 2

出力

– 4

説明

-長さ 2 で、ちょうど 2 つの母音を含む部分文字列は、「ae」、「ei」、「io」、「ou」です。

入力

– str = 'fghjsdfdffg'、K = 5、X = 1

出力

– 0

説明

- 文字列 str には母音が含まれていないため、母音を 1 つ含む部分文字列は見つかりません。 方法1

このメソッドでは、str の長さ K の各部分文字列を見つけます。その後、特定の部分文字列内の母音の総数を数え、それらが X に等しいことがわかった場合は、カウントを 1 増やします。

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

cntSubStr() 関数で、「cnt」変数をゼロに初期化して、部分文字列の合計数を格納します。

• ループを使用して、0 番目のインデックスから len - K インデックスまで反復します。ここで、「len」は文字列の長さです。

• ループ内で、substr() メソッドを使用して、i 番目のインデックスから始まる長さ K の部分文字列を取得します。

• countVowel() 関数を実行して、部分文字列内の母音の総数をカウントします。

• countVowel() 関数で、「vowels」変数をゼロに初期化し、母音の総数を保存します。

• 部分文字列をトラバースします。現在の文字は母音です。「母音」の値に 1 を加えます。

• 「母音」を返します。

• cntSubStr() 関数では、部分文字列内の母音の合計数が X に等しい場合、「cnt」の値を 1 増やします。

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

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー
  時間計算量
– O(N*K)、str を走査するとき、countVowel() 関数内の部分文字列を走査します。

空間複雑度

– 部分文字列を格納するためO(K)です

方法 2 スライディング ウィンドウ技術を使用して、この方法の問題を解決します。部分文字列から最初の文字を削除し、最後に 1 文字を追加します。さらに、現在の部分文字列内の母音の数を追跡し、それが X と等しい場合は、その数を 1 つ増やすことができます。

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

特定の文字が母音かどうかに基づいてブール値を返す isVowel() 関数を定義します。

cntSubStr() 関数で、「total_vow」を定義し、ゼロに初期化して、現在のウィンドウに母音の合計を保存します。

0 番目のインデックスから開始して、最初のウィンドウを表す長さ K の部分文字列内の母音の総数を見つけます。
「vow」の値が X に等しいかどうかに応じて、「cnt」変数を 1 または 0 に初期化します。
文字列の位置 1 から len – K インデックスまでのトラバースを開始します。
(i-1) 文字が母音の場合、「total_vow」の値を 1 減算します。
(i - 1 K) 番目のインデックスの文字が母音の場合、「total_vow」の値を 1 増やします。
「total_vow」が X と等しい場合、「cnt」を 1 増やします。
「cnt」の値を返します。

• ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー
文字列を反復処理するため、時間計算量 - O(N)。

• 余分なスペースを使用しないため、スペースの複雑さ - O(1)。

2 番目の方法を最適化し、コードの時間の複雑さを軽減しました。さらに、2 番目の方法の空間複雑性も最適化します。ここでは、正確に X 個の母音を含む、長さ K の部分文字列の合計数を求めますが、プログラマは、正確に K 個の母音を含む、任意の長さの部分文字列の合計数を見つけようとすることもできます。

以上が正確に X 個の母音を含む長さ K の部分文字列の数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。