K 個の異なる母音を含む最長の部分文字列

この記事では、指定された文字列内に K 個の異なる母音を含む最長の部分文字列を見つける問題を検討します。この問題は、C でさまざまなアルゴリズムを使用して解決できます。この問題は、コンピュータ サイエンスの分野、特にテキスト処理や自然言語処理タスクで頻繁に発生します。文字列を操作し、特殊なケースに対処する人の能力を検査します。

＃＃＃文法＃＃＃

C フィールドでは、クラス std::string が文字列データ型を表します。この多用途エンティティを使用して、文字シーケンスを保存および操作できます。

テンプレート クラス std::vector は動的配列の特性を具体化しており、配列のサイズを調整したり、カプセル化された要素に対して一連の操作を実行したりできます。

クラス テンプレートとして、std::unowned_map は順序なしマッピング構造をカプセル化します。これにより、キーが不一致のままの単一のキーと値のペアを保存でき、これらの異なるキーを使用して値を取得できます。

関数テンプレート std::max は、2 つの値の最大値を返します。この多用途メカニズムにより、> 演算子が正しく定義されていれば、あらゆるデータ型を簡単に比較できます。

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

＃＃＃＃＃＃始める＃＃＃＃＃＃

最長の部分文字列とその長さを格納する変数を初期化します。

• 文字列を反復処理して、K 個の異なる母音を持つ部分文字列を見つけます。

• 部分文字列の長さを比較し、それに応じて最長の部分文字列とその長さを更新します。

• すべての部分文字列が評価されるまで、手順 2 と 3 を繰り返します。

• 最長の部分文字列を返します。

＃＃＃＃＃＃仕上げる＃＃＃＃＃＃
• ＃＃＃方法＃＃＃

• 方法 1

  - ブルート フォース クラッキング

• 方法 2
- スライディング ウィンドウ

方法 1: ブルート フォース クラッキング

• この実装は、正確に k 個の一意の母音を持つ文字列の最長部分文字列を検出するための総当り手法を具体化しています。コードは、is_vowel と has_k_distinct_vowels という 2 つのヘルパー関数を定義することから始まります。 Example

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

• is_vowel 関数は 1 つの文字を入力として受け取り、その文字が母音 (「a」、「e」、「i」、「o」、「u」など) の場合は true を返し、それ以外の場合は false を返します。価値。この関数は、後に文字が母音であるかどうかを判断するために使用されました。 has_k_distinct_vowels 関数は、文字列と整数 k を入力として受け入れ、文字列にちょうど k 個の一意の母音が含まれる場合は true 値を返し、それ以外の場合は false 値を返します。この関数は、unordered_set を使用して文字列内の母音を記録し、文字列内の一意の母音の数をカウントします。

メイン関数longest_substring_bruteforceは、文字列と整数kを入力として受け取り、正確にk個の一意の母音を含む文字列内の最長の部分文字列を返します。

これは、2 つのネストされた for ループを利用して、文字列のすべての可能な部分文字列を反復処理することによって実現されます。部分文字列ごとに has_k_distinct_vowels 関数を呼び出して、部分文字列に正確に k 個の一意の母音が含まれているかどうかを確認します。

現在の部分文字列に k 個の一意の母音があり、現在の最長部分文字列よりも幅が広い場合、現在の部分文字列が新しい最長部分文字列になります。

最後に、コードは文字列と整数 k を入力し、longest_substring_bruteforce 関数を呼び出して、k 個の一意の母音を持つ最長の部分文字列を見つけ、結果を出力します。

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

方法 2: スライディング ウィンドウ

スライディング ウィンドウ法は、コンピューター サイエンスとアルゴリズムの問​​題を解決するために使用される手法です。これは、特定の入力内で特定の基準を満たす、部分文字列や部分配列などの特定のパターンを検索するために使用されます。

このメソッドでは、2 つのポインターを使用して、入力内をスライドするスライディング ウィンドウを作成します。ウィンドウのサイズは、必要な条件が確実に満たされるように、必要に応じて調整されます。このアルゴリズムは、個別の要素の数、要素の合計など、現在のウィンドウのプロパティを追跡します。

Example

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

Example

is_vowel 関数は、指定された文字が母音 (つまり、a、e、i、o、または u) の場合に true を返すヘルパー関数です。

メイン関数longest_substring_slidingwindowは、文字列sと整数kを入力として受け入れます。左右の 2 つのポインターを使用してスライディング ウィンドウを作成し、文字列を反復処理します。

順序なしマップの頻度を使用して、現在のウィンドウ内の各母音の頻度を追跡します。ウィンドウ内の母音の周波数が k を超えた場合は、母音の周波数が再び k に等しくなるまで左ポインタを右に移動します。現在のウィンドウの長さは右 - 左 1 として計算され、これまでに確認された最大長を超える場合は、開始インデックスと長さが更新されます。

最後に、この関数は文字列クラスの substr メソッドを使用して、k 個の異なる母音を含む最長の部分文字列を返します。

#include <iostream>
#include <string>
#include <unordered_map>

bool is_vowel(char c) {
   return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

std::string longest_substring_slidingwindow(const std::string &s, int k) {
   int left = 0, right = 0, max_len = 0, start = 0;
   std::unordered_map<char, int> freq;

   while (right < s.size()) {
      char c = s[right];
      if (is_vowel(c)) {
         freq[c]++;
      }

      while (freq.size() > k) {
         char left_char = s[left];
         if (is_vowel(left_char)) {
            freq[left_char]--;
            if (freq[left_char] == 0) {
               freq.erase(left_char);
            }
         }
         left++;
      }

      if (freq.size() == k && (right - left + 1) > max_len) {
         max_len = right - left + 1;
         start = left;
      }

      right++;
   }

   return s.substr(start, max_len);
}

int main() {
   std::string input = "aeiaaioooaauuaeiu";
   int k = 3;
   std::string result = longest_substring_slidingwindow(input, k);
   std::cout << "Longest substring with " << k << " distinct vowels: " << result << std::endl;
   return 0;
}

输出

Longest substring with 3 distinct vowels: iaaioooaa

结论

在本文中，我们讨论了两种方法来解决在给定字符串中找到包含K个不同元音字母的最长子串的问题。第一种方法是暴力法，而第二种方法是滑动窗口法。暴力法的时间复杂度为O(n^3)，使其成为更适合处理较大输入的解决方案。滑动窗口法由于其较低的时间复杂度，推荐用于解决这个问题。

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