数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究包含所有元音的最小子字符串的长度
在字符串操作任务中遇到的一个常见问题涉及识别包含每个元音至少一次的最短子字符串。此任务在其应用中包含各种领域，例如数据分析、生物信息学和自然语言处理等。这里的目标是找出现有字符串中哪个最小的连续部分至少包含这五个字母（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。为了描绘滑动窗口，我们还利用指向左侧和右侧的两个指针。
如果当前字符是元音，我们首先通过将其添加到 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
算法
步骤 1 - 设置开始和结束指针，它们分别指向字符串的开头。
步骤 2 - 继续将结束指针向右移动，直到发现仅包含元音的子字符串。
步骤 3 - 如果我们找到一个包含所有元音的子字符串，则将开始指针向右移动，直到它不再包含所有元音。
步骤 4 - 继续将结束指针向右移动，直到发现一个新的包含所有元音的子字符串，然后将开始指针向右移动，直到子字符串不再包含所有元音。
步骤 5 - 刷新迄今为止最短的子字符串长度。
示例 2
在本例中，我们保留两个指针 left 和 right 来表示滑动窗口。我们从左到右遍历字符串 str，每次检查当前字符是否为元音。为了跟踪迄今为止观察到的元音，如果它是元音，我们将其添加到集合 seen 中。
一旦 seen 包含所有元音，我们就移动左指针以减小子字符串的长度。此过程一直持续到右指针到达字符串的末尾。
然后返回包含所有元音的最小子字符串的长度。在不存在此类子字符串的情况下，我们返回 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 - 从大小为 5 的频率数组开始，以记录每个元音（a、e、i、o、u）的重复次数。
步骤 2 - 创建开始和结束指针，分别突出显示字符串的开头。
步骤 3 - 继续将结束指针向右移动，直到每个元音至少被听到一次。
步骤 4 - 在每个元音至少重复一次后，将开始指针向右移动，直到子字符串不再包含所有元音。
步骤 5 - 调整迄今为止识别的子字符串的最小长度，然后将结束指针向右移动，直到发现一个新的包含所有元音的子字符串。
步骤 6 - 在每个位置更新频率数组，以验证当前子字符串是否包含所有元音。
示例 3
在本例中，函数 minLengthSubstring 将字符串作为输入，并计算包含所有五个元音（a、e、i、o、u）的最小子字符串的长度。
该函数使用名为 vowelCount 的频率数组计算子字符串中的每个元音。它通过维护计数 distinctVowels 来跟踪子字符串中不同元音的数量。
该函数使用两个指针 start 和 finish 遍历字符串，并为遇到的每个元音增加频率数组 vowelCount。一旦找到每个不同的元音，子字符串就会从起始位置开始缩小，直到没有剩余的不同元音。如果发现较短的子字符串，则更新子字符串的最小长度。
主函数使用字符串来演示如何使用 minLengthSubstring 方法，方法是输入包含所有元音的最小子字符串的长度。
#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
结论
总之，查找包含所有元音的最小子字符串的长度是一个可以使用各种技术有效解决的问题。通过采用滑动窗口法或对元音的出现进行哈希处理，可以遍历字符串并识别满足要求的最小子字符串。这些方法的时间复杂度通常是线性的，因此适用于大型输入。但是，务必处理边缘情况并考虑可能影响解决方案的其他约束条件。总的来说，使用正确的算法方法，可以有效地确定包含所有元音的最小子字符串的长度。
162 次查看
