すべての母音を含む最小の部分文字列の長さ

文字列操作タスクでよく遭遇する一般的な問題は、各母音を少なくとも 1 回含む最短の部分文字列を特定することです。このタスクは、データ分析、バイオインフォマティクス、自然言語処理などのさまざまな分野に応用できます。目標は、これら 5 つの文字 (a、e、i、o、u) を少なくとも 1 回含む既存の文字列の最小の連続部分を見つけることです。この課題を解決するための選択プロセスには、スライディング ウィンドウ アルゴリズムの実装、ハッシュ プロセスの使用、正規表現の活用など、さまざまな手法が含まれます。実際のシナリオの多くは信頼性の高いテキスト操作方法を必要とするため、この問題に対する堅牢な解決策を見つけることが重要になることがよくあります。

＃＃＃方法＃＃＃

すべての母音を含む最小の部分文字列の長さを見つけるにはさまざまな方法があります。

方法 1. スライディング ウィンドウ方法

方法 2. ダブル ポインターによる方法

方法 3. 周波数アレイ法

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

各文字列内のすべての母音を含む最短の部分文字列のサイズをすばやく決定するには、スライディング ウィンドウ法を使用します。このメソッドは、「左」と「右」と呼ばれることが多い 2 つのポインターを利用して、文字列に沿ってスライドするスライディング ウィンドウを生成します。

＃＃＃文法＃＃＃

スライディング ウィンドウ法を使用してすべての母音を含む最小部分文字列長を見つけるための構文は次のとおりです -

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

ステップ 1

- サイズ n (文字列の長さ) のスライディング ウィンドウを使用して、左から右に移動します。

ステップ 2

- ウィンドウ内の各位置で、部分文字列が完全に母音で構成されていることを確認します。その場合は、これまでに見つかった部分文字列の最小長を更新します。

ステップ 3

- ハッシュ テーブルを使用して部分文字列内の各母音の繰り返し数を記録し、部分文字列にすべての母音が含まれているかどうかを判断します。

ステップ 4

- 部分文字列にすべての母音が含まれていない場合は、ウィンドウを右に移動してテストを続行し、すべての潜在的な部分文字列のテストが完了するまでプロセスを繰り返します。 例 1

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

例 1 この実装では、指定された文字が母音であるかどうかを判断するために、ヘルパー関数 isVowel を定義します。スライディング ウィンドウを説明するために、左右の 2 つのポインターも使用します。

現在の文字が母音の場合、最初に while ループ内のウィンドウ コレクションにウィンドウを追加してウィンドウを拡張します。次に、ウィンドウ コレクションのサイズが 5 (つまり、すべての母音が存在する) であることを確認します。その場合は、応答を変更し、ウィンドウ セットから左端の文字を 5 未満になるまで削除してウィンドウのサイズを縮小します。

ループの結果は、すべての母音を含む最小の部分文字列の長さを返します。

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

方法 2: ダブル ポインター方法

ダブル ポインター法は、さまざまな文字列操作の問題を迅速に解決するための一般的な方法です。 2 ポインター手法は、すべての母音を含む最小の部分文字列の長さを決定するのに非常に役立ちます。

＃＃＃文法＃＃＃

これは、ダブル ポインター法を使用して、すべての母音を含む部分文字列の最小長を見つけるための構文です。 -

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

ステップ 1

- 開始ポインターと終了ポインターがそれぞれ文字列の開始位置を指すように設定します。

ステップ 2

- 母音のみを含む部分文字列が見つかるまで、終了ポインタを右に移動し続けます。

ステップ3

-すべての母音を含む部分文字列が見つかった場合は、すべての母音が含まれなくなるまで開始カーソルを右に移動します。

ステップ4 -すべての母音を含む新しい部分文字列が見つかるまで末尾ポインタを右に移動し続け、その後、部分文字列にすべての母音が含まれなくなるまで開始ポインタを右に移動します。

ステップ 5 - これまでの最短の部分文字列長を更新します。

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

この例では、スライディング ウィンドウを表すために、左右の 2 つのポインターを保持します。左から右に、文字列 str を反復処理し、そのたびに現在の文字が母音かどうかを確認します。これまでに観察された母音を追跡するために、それが母音であれば、それを観察されたセットに追加します。 部分文字列にすべての母音が含まれていることを確認したら、左カーソルを移動して部分文字列の長さを減らします。このプロセスは、右カーソルが文字列の末尾に到達するまで続きます。

すべての母音を含む最短の部分文字列の長さを返します。そのような部分文字列が存在しない場合は、0 が返されます。 リーリー ＃＃＃出力＃＃＃ リーリー 方法 3. 周波数アレイ法

頻度配列法を使用して、各文字列内のすべての母音を含む最短の部分文字列を測定します。母音の出現数を記録する頻度配列を構築し、テキストを繰り返し処理して目的の部分文字列を見つける必要があります。

＃＃＃文法＃＃＃

すべての母音を含む最小の部分文字列を見つけるための構文は次のとおりです -

# Check if all vowels are present in the current substring
if all(freq[vowel] > 0 for vowel in vowels):
   # Update the minimum length if needed
   min_length = min(min_length, right - left + 1)
    
   # Move the left pointer to find a potentially smaller substring
   while left < right:
      freq[input_string[left]] -= 1
      if freq[input_string[left]] == 0:
      break
      left += 1

# Move the right pointer to expand the current substring
right += 1

算法

步骤 1 − 为了记录每个元音字母（a，e，i，o，u）的重复次数，从大小为5的频率数组开始。

第二步 - 创建开始和结束指针，分别标记字符串的开头。

第三步 - 继续将结束指针向右移动，直到每个元音字母至少被听到一次。

步骤4 − 将起始指针向右移动，直到子字符串不再包含至少每个元音字母的重复。

第五步 - 调整已经识别出的子字符串的最小长度，然后将结束指针向右移动，直到发现一个包含所有元音字母的新子字符串。

步骤 6 - 在每个位置更新频率数组，以验证当前子字符串是否包含所有元音字母。

Example 3

的中文翻译为：

示例3

在这个例子中，函数min Length Substring接受一个字符串作为输入，并计算包含所有五个元音字母（a，e，i，o，u）的最小子字符串的长度。

该函数使用名为vowelCount的频率数组来计算子字符串中的每个元音字母的数量。它通过维护一个名为distinctVowels的计数器来跟踪子字符串中不同元音字母的数量。

通过使用两个指针，即start和finish，该函数循环遍历字符串，对每个遇到的元音字母增加频率数组的vowelCount。一旦找到了每个不同的元音字母，子字符串就开始从起始位置收缩，直到没有不同的元音字母为止。如果发现了更短的子字符串，则更新最小子字符串的长度。

主要功能使用字符串来展示如何使用最小长度子字符串方法，通过输入包含所有元音字母的最短子字符串的长度。

#include <iostream>
#include <climits>
using namespace std;

int minLengthSubstring(const string& str) {
   const string vowels = "aeiou";
   int vowelCount[5] = {0};  // Frequency array for vowels
   int distinctVowels = 0;  // Count of distinct vowels in the substring

   // Initialize the minimum length to maximum integer value
   int minLength = INT_MAX;

   int start = 0, end = 0;
   while (end < str.length()) {
      // Increment frequency for vowel at 'end' position
      for (int i = 0; i < 5; i++) {
         if (str[end] == vowels[i]) {
            if (vowelCount[i] == 0) {
               distinctVowels++;
            }
            vowelCount[i]++;
            break;
         }
      }

      // If all distinct vowels are found
      if (distinctVowels == 5) {

         while (start < end) {
            // Update minimum length if a shorter substring is found
            if (minLength > end - start + 1) {
               minLength = end - start + 1;
            }

            // Decrement frequency for vowel at 'start' position
               for (int i = 0; i < 5; i++) {
               if (str[start] == vowels[i]) {
                  vowelCount[i]--;
                  if (vowelCount[i] == 0) {
                     distinctVowels--;
                  }
                  break;
               }
            }
            start++;

            // Break if any distinct vowel is missing in the substring
            if (distinctVowels < 5) {
               break;
            }
         }
      }

      end++;
   }

   return minLength == INT_MAX ? -1 : minLength;
}

int main() {
   string str = "aeeioubcdofu";
   int length = minLengthSubstring(str);

   if (length == -1) {
      cout << "No substring containing all vowels found." << endl;
   } else {
      cout << "Length of the smallest substring containing all vowels: " << length << endl;
   }
   return 0;
}

输出

Length of the smallest substring containing all vowels: 6

结论

总之，找到すべての母音を含む最小の部分文字列の長さ是一个可以使用各种技术高效解决的问题。通过使用滑动窗口方法或散列元音字母的出现次数，可以遍历字符串并识别满足要求的最小子字符串。这些方法的时间复杂度通常是线性的，适用于大规模输入。然而，重要的是处理边界情况并考虑可能影响解决方案的额外约束条件。总的来说，通过正确的算法方法，可以有效地确定すべての母音を含む最小の部分文字列の長さ。

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