정확히 X개의 모음을 포함하는 길이가 K인 부분 문자열의 수

이 문제에서는 정확히 K개의 모음을 포함하는 길이가 K인 부분 문자열의 총 개수를 찾아야 합니다. 우리는 문제를 해결하는 두 가지 다른 방법을 살펴보겠습니다. 간단한 방법을 사용하여 길이 K의 각 하위 문자열에서 모음 수를 확인할 수 있습니다. 또한 이 문제를 해결하기 위해 슬라이딩 윈도우 접근 방식을 사용할 수 있습니다.

문제 설명 - 알파벳 소문자와 대문자를 포함하는 길이 N의 문자열 str이 제공됩니다. 정확히 X개의 모음을 포함하는 길이가 K인 부분 문자열의 총 개수를 계산해야 합니다.

예

Input – str = "TutorialsPoint", K = 3, X = 2

출력– 6

설명 – 정확히 2개의 모음을 포함하는 길이 3의 하위 문자열은 'uto', 'ori', 'ria', 'ial', 'Poi' 및 'oin'입니다. p>

Input – str = 'aeiou', K = 2, X = 2

출력– 4

설명- 길이가 2이고 정확히 2개의 모음을 포함하는 하위 문자열은 'ae', 'ei', 'io' 및 'ou'입니다.

Input – str = 'fghjsdfdffg', K = 5, X = 1

출력– 0

설명- 문자열 str에는 모음이 포함되어 있지 않으므로 모음 1개를 포함하는 하위 문자열을 찾을 수 없습니다.

방법 1

이 방법에서는 str의 길이가 K인 모든 하위 문자열을 찾습니다. 그런 다음 특정 하위 문자열의 총 모음 수를 계산하고 해당 모음이 X와 같다면 개수를 1씩 늘릴 수 있습니다.

알고리즘

• cntSubStr() 함수에서 "cnt" 변수를 0으로 초기화하여 전체 하위 문자열 수를 저장합니다.

• 루프를 사용하여 0번째 인덱스부터 len - K 인덱스까지 반복합니다. 여기서 "len"은 문자열 길이입니다.

• 루프에서 substr() 메서드를 사용하여 i번째 인덱스부터 시작하여 길이가 K인 부분 문자열을 가져옵니다.

• countVowel() 함수를 실행하여 하위 문자열의 총 모음 수를 계산합니다.

• countVowel() 함수에서 "vowels" 변수를 0으로 초기화하여 총 모음 수를 저장합니다.

• 하위 문자열을 순회하면 현재 문자가 모음이고 'vowels' 값에 1을 추가합니다.

• "모음"으로 돌아갑니다.

• cntSubStr() 함수에서 하위 문자열의 총 모음 수가 X와 같으면 "cnt" 값을 1만큼 늘립니다.

• "cnt"의 값을 반환합니다.

예

으아악

출력

으아악

시간 복잡성 – O(N*K), str을 반복할 때 countVowel() 함수의 하위 문자열을 반복합니다.

공간 복잡도 – 부분 문자열을 저장하므로 O(K)

방법 2

이러한 접근 방식의 문제를 해결하기 위해 슬라이딩 윈도우 기술을 사용하겠습니다. 하위 문자열에서 첫 번째 문자를 제거하고 끝에 문자 1개를 추가합니다. 또한 현재 하위 문자열의 모음 개수를 추적하고 X와 같으면 개수를 1씩 늘릴 수 있습니다.

알고리즘

• 특정 문자가 모음인지 여부에 따라 부울 값을 반환하도록 isVowel() 함수를 정의합니다.

• cntSubStr() 함수에서 "total_vow"를 정의하고 0으로 초기화하여 현재 창에 총 모음을 저장합니다.

• 0번째 인덱스부터 시작하여 첫 번째 창을 나타내는 길이 K의 하위 문자열에 있는 모음의 총 개수를 찾습니다.

• "vow" 값이 X인지 여부에 따라 "cnt" 변수를 1 또는 0으로 초기화합니다.

• 위치 1부터 len – K 인덱스까지 문자열 탐색을 시작합니다.

• (i-1) 문자가 모음인 경우 "total_vow" 값을 1씩 감소시킵니다.

• (i - 1 + K)번째 인덱스의 문자가 모음인 경우 "total_vow" 값을 1 증가시킵니다.

• "total_vow"가 X와 같으면 "cnt"를 1만큼 늘립니다.

• "cnt"의 값을 반환합니다.

예

으아악

출력

으아악

시간 복잡도 - 문자열을 반복하므로 O(N)입니다.

공간 복잡도 - 추가 공간을 사용하지 않으므로 O(1)입니다.

두 번째 방법을 최적화하고 코드의 시간 복잡도를 줄였습니다. 또한 두 번째 방법의 공간 복잡도도 최적화합니다. 여기서 우리는 정확히 X 모음을 포함하는 길이가 K인 부분 문자열의 총 개수를 찾을 수 있지만, 프로그래머는 정확히 K 개의 모음을 포함하는 모든 길이의 부분 문자열의 총 개수를 찾으려고 할 수 있습니다.

위 내용은 정확히 X개의 모음을 포함하는 길이가 K인 부분 문자열의 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!