모든 모음을 포함하는 가장 작은 부분 문자열의 길이

문자열 조작 작업에서 자주 직면하는 일반적인 문제는 각 모음을 한 번 이상 포함하는 가장 짧은 부분 문자열을 식별하는 것입니다. 이 작업은 데이터 분석, 생물정보학, 자연어 처리 등 다양한 분야에 응용될 수 있습니다. 목표는 이 다섯 글자(a, e, i, o, u)를 적어도 한 번 포함하는 기존 문자열에서 가장 작은 연속 부분을 찾는 것입니다. 이 과제를 해결하기 위한 선택 프로세스에는 슬라이딩 윈도우 알고리즘 구현, 해싱 프로세스 사용, 정규식 활용 등 다양한 기술이 포함됩니다. 많은 실제 시나리오에는 신뢰할 수 있는 텍스트 조작 방법이 필요하기 때문에 이 문제에 대한 강력한 솔루션을 찾는 것이 종종 중요합니다.

방법

모든 모음을 포함하는 가장 작은 부분 문자열의 길이를 찾는 방법은 다양합니다.

방법 1. 슬라이딩 윈도우 방식

방법 2. 더블 포인터 방법

방법 3. 주파수 배열 방식

방법 1: 슬라이딩 윈도우 방식

각 문자열의 모든 모음을 포함하는 가장 짧은 하위 문자열의 크기를 빠르게 확인하려면 슬라이딩 윈도우 방법을 사용하세요. 이 방법은 "왼쪽"과 "오른쪽"이라고 불리는 두 개의 포인터를 활용하여 문자열을 따라 미끄러지는 슬라이딩 창을 생성합니다.

문법

슬라이딩 윈도우 방법을 사용하여 모든 모음을 포함하는 최소 부분 문자열 길이를 찾는 구문은 다음과 같습니다. -

으아악

알고리즘

1단계 - 크기 n(끈의 길이)의 슬라이딩 창을 사용하여 왼쪽에서 오른쪽으로 이동합니다.

2단계 - 창의 각 위치에서 하위 문자열이 모두 모음으로 구성되어 있는지 확인하세요. 그렇다면 지금까지 찾은 하위 문자열의 최소 길이를 업데이트하세요.

3단계 - 해시 테이블을 사용하여 하위 문자열에 있는 각 모음의 반복 횟수를 기록하여 하위 문자열에 모든 모음이 포함되어 있는지 확인합니다.

4단계 - 하위 문자열에 모음이 모두 포함되지 않은 경우 창을 오른쪽으로 이동하고 모든 잠재적 하위 문자열이 테스트될 때까지 프로세스를 반복하여 테스트를 계속합니다.

예제 1

의 중국어 번역은 다음과 같습니다.

예제 1

이 구현에서는 주어진 문자가 모음인지 확인하기 위해 도우미 함수 isVowel을 정의합니다. 슬라이딩 윈도우를 설명하기 위해 왼쪽과 오른쪽에 두 개의 포인터도 사용합니다.

현재 문자가 모음이면 먼저 while 루프 내부의 창 모음에 추가하여 창을 확장합니다. 그런 다음 창 컬렉션의 크기가 5(즉, 모든 모음이 있음)인지 확인합니다. 그렇다면 응답을 수정하고 창 집합에서 가장 왼쪽 문자를 5보다 작아질 때까지 제거하여 창 크기를 줄입니다.

루프 결과는 모든 모음을 포함하는 가장 작은 하위 문자열의 길이를 반환합니다.

으아악

출력

으아악

방법 2: 이중 포인터 방법

이중 포인터 방법은 다양한 문자열 조작 문제를 빠르게 해결하는 데 널리 사용되는 방법입니다. 이중 포인터 기술은 모든 모음을 포함하는 가장 작은 하위 문자열의 길이를 결정하는 데 매우 유용합니다.

문법

이것은 이중 포인터 방법을 사용하여 모든 모음을 포함하는 최소 부분 문자열 길이를 찾는 구문입니다−

으아악

알고리즘

1단계 - 시작 포인터와 끝 포인터가 각각 문자열의 시작 위치를 가리키도록 설정합니다.

2단계 - 모음만 포함된 하위 문자열을 찾을 때까지 끝 포인터를 오른쪽으로 계속 이동하세요.

3단계 − 모든 모음이 포함된 하위 문자열을 찾으면 더 이상 모든 모음이 포함되지 않을 때까지 시작 커서를 오른쪽으로 이동합니다.

4단계 − 모든 모음이 포함된 새 하위 문자열을 찾을 때까지 꼬리 포인터를 오른쪽으로 계속 이동한 다음 하위 문자열에 더 이상 모든 모음이 포함되지 않을 때까지 시작 포인터를 오른쪽으로 이동합니다.

5단계 - 지금까지 가장 짧은 부분 문자열 길이를 새로 고칩니다.

예 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!