資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
