包含所有元音字母的最小子字串的長度

在字串操作任務中經常遇到的一個常見問題是識別包含每個元音字母至少一次的最短子字串。這個任務在數據分析、生物資訊學和自然語言處理等各個領域都有應用。目標是找出現有字串中包含這五個字母（a，e，i，o，u）至少一次的最小連續部分。解決這個挑戰的選擇過程包括多種技術，例如實現滑動視窗演算法、使用雜湊過程或利用正規表示式等等。找到這個問題的穩健解決方案通常變得至關重要，因為許多現實場景需要可靠的文字操作方法。

方法

有各種方法可以找到包含所有元音字母的最小子字串的長度。

方法1. 滑動視窗方法

方法2. 雙指標方法

方法3. 頻率數組方法

方法一：滑動視窗方法

為了快速確定包含每個字串中的所有元音字母的最短子字串的大小，請使用滑動視窗方法。該方法利用兩個指針，通常稱為“left”和“right”，產生一個滑動窗口，沿著字串滑動。

文法

這裡是使用滑動視窗方法找到包含所有元音字母的最小子字串長度的語法 -

def find_smallest_substring(string):
   vowels = {'a', 'e', 'i', 'o', 'u'}
   unique_vowels = set()
   start = 0
   end = 0
   min_length = float('inf')
    
   while end < len(string):
      # Expand the window
      if string[end] in vowels:
         unique_vowels.add(string[end])
        
      # Contract the window
      while len(unique_vowels) == len(vowels):
         min_length = min(min_length, end - start + 1)
         if string[start] in vowels:
         unique_vowels.remove(string[start])
         start += 1
        
       end += 1
    
   return min_length

演算法

步驟 1 - 使用一個大小為 n（字串的長度）的滑動窗口，並從左到右移動它。

步驟 2 - 在視窗的每個位置，確保子字串完全由母音字母組成。如果是，則更新迄今為止發現的子字串的最小長度。

步驟 3 - 使用雜湊表來記錄子字串中每個元音字母的重複次數，以確定子字串是否包含所有元音字母。

第四步 - 如果子字串不包含所有的元音字母，則透過將視窗向右移動並重複該過程，繼續進行測試，直到所有潛在的子字串都被測試完。

Example 1

的中文翻譯為：

範例1

要確定在這個實作中給定的字元是否是元音字母，我們定義了輔助函數 isVowel。為了描述滑動窗口，我們也利用了左右兩個指針。

如果當前字元是元音字母，我們首先透過將其新增至while循環內的視窗集合來擴展視窗。然後驗證視窗集合的大小是否為5（即，所有元音字母都存在）。如果是，則修改回應並透過從視窗集合中消除最左邊的字元來減小視窗的大小，直到小於5。

循環的結果傳回包含所有元音字母的最小子字串的長度。

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

bool isVowel(char c) {
   return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int smallestSubstring(string s) {
   unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
   unordered_set<char> window;
   int n = s.length(), left = 0, right = 0, ans = n + 1;
    
   while (right < n) {
      // Expand the window by adding the current character
      char c = s[right];
      if (isVowel(c)) {
         window.insert(c);
      } 
      right++;
        
      // close the window by removing the leftmost character
      while (window.size() == 5) {
         ans = min(ans, right - left);
         char d = s[left];
         if (isVowel(d)) {
            window.erase(d);
         }
         left++;
      }
   }
   return ans <= n ? ans : 0;
}

int main() {
   string s = "aeeioubcdfuioaei";
   int len = smallestSubstring(s);
   cout << "Length of smallest substring containing all vowels: " << len << endl;
   return 0;
}

輸出

Length of smallest substring containing all vowels: 6

方法2：雙指標法

雙指標方法是一種受歡迎的快速解決各種字串操作問題的方法。雙指標技術在確定包含所有元音字母的最小子字串的長度方面非常有幫助。

文法

這是使用雙指標方法找到包含所有元音字母的最小子字串長度的語法−

function findSmallestSubstring(str):
   vowels = {'a', 'e', 'i', 'o', 'u'}
   count = 0
   left = 0
   minLength = infinity

   for right in range(length of str):
      if str[right] is a vowel:
         count += 1

       while count is same as the total number of vowels:
         minLength = minimum (minLength, right - left + 1)

         if str[left] is a vowel:
         count -= 1

         left += 1

   return minLength

演算法

第一步 - 設定起始和結束指針，分別指向字串的起始位置。

第二步 - 繼續將結束指標向右移動，直到發現一個只包含元音字母的子字串。

步驟 3 − 如果我們找到一個包含所有元音字母的子字串，則將起始遊標向右移動，直到不再包含所有元音字母。

步驟4 − 繼續將尾指標向右移動，直到發現一個包含所有元音字母的新子字串，然後將起始指標向右移動，直到子字串不再包含所有元音字母。

第五步 - 刷新到目前為止的最短子字串長度。

Example 2

的中文翻譯為：

範例2

在這個例子中，為了表示滑動窗口，我們保留了兩個指針，left和right。從左到右，我們遍歷字串str，每次檢查當前字元是否是元音字母。為了保持追蹤到目前為止觀察到的元音字母，如果是元音字母，我們將其添加到集合viewed中。

我們將左遊標移動以減少子字串的長度，一旦看到的子字串包含了所有的元音字母。這個過程會一直進行，直到右邊遊標到達字串的末端。

傳回包含所有元音字母的最短子字串的長度。如果不存在這樣的子字串，則傳回0。

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int smallestSubstringLength(const string& str) {
   int n = str.length();
   unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};

   unordered_set<char> seen;
   int left = 0, right = 0;
   int smallestLength = n + 1;

   while (right < n) {
      if (vowels.find(str[right]) != vowels.end()) {
         seen.insert(str[right]);
      }

      if (seen.size() == vowels.size()) {
         while (seen.size() == vowels.size()) {
            if (right - left + 1 < smallestLength) {
               smallestLength = right - left + 1;
            }

            if (vowels.find(str[left]) != vowels.end()) {
               seen.erase(str[left]);
            }

            left++;
         }
      }
      right++;
   }
   return (smallestLength == n + 1) ? 0 : smallestLength;
}

int main() {
   string str = "aeeiiouuobcdaeiou";
   int length = smallestSubstringLength(str);
   cout << "Length of the smallest substring containing all vowels: " << length << endl;
   return 0;
}

輸出

Length of the smallest substring containing all vowels: 7

方法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中文網其他相關文章！