当前位置：极客笔记 > C++ > C++ 精选笔记 > C++ 包含所有元音字母的最短子字符串的长度

C++ 包含所有元音字母的最短子字符串的长度

C++ 包含所有元音字母的最短子字符串的长度

在字符串操作任务中常遇到的一个问题是识别出至少包含一次每个元音字母的最短子字符串。此任务在数据分析、生物信息学、自然语言处理等各个领域中都有应用。目标是找出现有字符串中具有这五个字母(a,e,i,o,u)至少一次的最小连续部分。解决这个挑战的选择过程包括多种技术，如实现滑动窗口算法、引入哈希过程或利用正则表达式等。寻找这个问题的稳健解决方案通常至关重要，因为许多现实场景需要可靠的文本操作方法。

方法

有多种方法可以找到包含所有元音字母的最短子字符串的长度。

方法1. 滑动窗口方法

方法2. 双指针方法

方法3. 频率数组方法

方法1：滑动窗口方法

为了快速确定包含每个字符串中的每个元音字母的最短子字符串的大小，可以使用滑动窗口方法。该方法使用两个指针，通常称为“左”和“右”，生成一个沿字符串滑动的滑动窗口。

语法

下面是找到包含所有元音字母的最短子字符串的长度的滑动窗口方法的语法 –

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 - 使用哈希表记录子字符串中每个元音字母的重复次数，以判断子字符串是否包含所有元音字母。

步骤4 - 如果子字符串不包含所有元音字母，通过将窗口向右移动并重复该过程，继续测试所有潜在的子字符串。

示例1

为了确定给定的字符是否为元音字母，我们定义了辅助函数isVowel。为了描述滑动窗口，我们还使用了左指针和右指针。

如果当前字符是元音字母，我们首先通过将其添加到窗口集合中来扩展窗口。然后，验证窗口集合的大小是否为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

步骤

第一步 - 设置起始和结束指针，分别指向字符串的起始位置。

第二步 - 继续将结束指针向右移动，直到发现一个只包含元音字母的子字符串。

第三步 - 如果我们找到一个包含所有元音字母的子字符串，将起始光标向右移动，直到它不再包含所有元音字母。

第四步 - 继续将结束指针向右移动，直到发现一个新的子字符串，该子字符串包含所有元音字母，然后将起始指针向右移动，直到该子字符串不再包含所有元音字母。

第五步 - 更新迄今为止的最短子字符串长度。

示例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的频率数组开始。

步骤2 − 创建开始和结束指针，分别标记字符串的起始位置。

步骤3 − 继续将结束指针向右移动，直到每个元音字母至少出现一次。

步骤4 − 将开始指针向右移动，直到子字符串不再包含所有元音字母，而是至少重复了每个元音字母一次为止。

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

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

示例3

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

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

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

main函数使用字符串来演示如何使用min Length Substring方法，通过输入包含所有元音字母的最短子字符串的长度。

#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

结论

总之，找到包含所有元音字母的最短子字符串的长度是一个可以通过各种技巧高效解决的问题。通过使用滑动窗口方法或者使用哈希表记录元音字母的出现次数，可以遍历字符串并找出满足要求的最小子字符串。这些方法的时间复杂度通常是线性的，适用于大规模输入。然而，处理边缘情况并考虑可能影响解决方案的其他限制条件是很重要的。总的来说，通过正确的算法方法，可以有效确定包含所有元音字母的最短子字符串的长度。

Camera课程

Camera API2 教程

API2 教程
Camera 性能教程

Perf 教程
Camera Native Framework 教程

Native FW 教程
Camera QCOM ISP 教程

ISP 教程
Camera QCOM Sensor 教程

Sensor 教程

Python教程

Python 教程

Python 教程
NumPy 教程

NumPy 教程
Django 教程

Django 教程

Java教程

Java 教程

Java 教程

Web教程

JavaScript 教程

JavaScript 教程
jQuery 教程

jQuery 教程
CSS 教程

CSS 教程
PHP 教程

PHP 教程
Laravel 教程

Laravel 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程

数据库教程

SQL 教程

SQL 教程
SQLite 教程

SQLite 教程
MySQL 教程

MySQL 教程
PL/SQL 教程

PL/SQL 教程
MongoDB 教程

MongoDB 教程

图形图像教程

OpenCV 教程

OpenCV 教程

办公软件教程

Excel 教程

Excel 教程

Linux教程

Linux命令全集

Linux命令全集
Linux内核API

Linux内核API
LVGL 教程

LVGL 教程

计算机教程

操作系统 教程

操作系统 教程
计算机网络 教程

计算机网络 教程
C语言 教程

C语言 教程
C++ 教程

C++ 教程
Swift 教程

Swift 教程

大数据教程

Hadoop 教程

Hadoop 教程
Spark 教程

Spark 教程
Scala 教程

Scala 教程

开发工具教程

Git 教程

Git 教程
Jenkins 教程

Jenkins 教程
ChatGPT 教程

ChatGPT 教程
IntelliJ 教程

IntelliJ 教程

C++ 精选教程