소문자와 대문자의 수가 동일한 하위 문자열의 수

이 문제에서는 주어진 문자열에서 동일한 수의 소문자와 대문자가 포함된 문자열의 총 개수를 계산해야 합니다. 이 문제를 해결하는 순진한 방법은 모든 하위 문자열을 찾아 소문자와 대문자 수가 동일한 하위 문자열의 총 개수를 계산하는 것입니다.

효율적인 접근 방식은 하위 배열 합산 문제를 사용하는 것입니다. 소문자를 -1로, 대문자를 +1로 처리할 수 있으며 문제를 해결하는 두 가지 방법을 모두 배우게 됩니다.

문제 설명- 알파벳 소문자와 대문자가 포함된 문자열 str이 제공됩니다. 동일한 수의 소문자와 대문자를 포함하는 부분 문자열의 총 개수를 계산해야 합니다.

예

입력 – str = 'TutOR'

출력 – 4

설명 – 4개의 하위 문자열인 'Tu', 'TutO', 'tO' 및 'utOR'을 얻을 수 있습니다. 여기에는 동일한 수의 소문자와 대문자가 포함됩니다

입력 – str = 'abcd'

출력 – 0

설명 – 문자열에 소문자만 포함되어 있기 때문에 동일한 소문자와 대문자를 포함하는 하위 문자열을 가져올 수 없습니다

입력 – str = 'XYz'

출력– 1

설명 - 'Yz' 하위 문자열만 얻을 수 있습니다.

방법 1

이것은 문제를 해결하는 순진한 방법입니다. 3개의 중첩 루프를 사용하여 주어진 문자열의 모든 하위 문자열을 찾습니다. 각 하위 문자열에 동일한 수의 소문자와 대문자가 포함되어 있는지 확인합니다. 그렇다면 개수를 1씩 증가시킵니다.

알고리즘

• 변수 'cnt'를 정의하고 0으로 초기화하세요.

• for 루프를 사용하여 문자열을 탐색하세요

• 루프에서 'upperCase' 및 'lowerCase' 변수를 정의하고 0으로 초기화합니다.

• i번째 인덱스부터 시작하는 문자열을 반복하려면 코드에 또 다른 중첩 루프를 추가하세요. 이런 식으로 i번째 인덱스부터 j번째 인덱스까지 부분 문자열을 얻을 수 있습니다

• 중첩 루프에서 문자가 대문자인 경우 대문자 변수의 값을 1씩 늘립니다. 그렇지 않으면 소문자 변수의 값을 1씩 늘립니다.

• 'upperCase' 변수와 'lowerCase' 변수의 값이 같으면 'cnt' 값을 1 증가시킵니다.

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

Example

Example

출력

시간 복잡도 - 모든 하위 문자열을 찾기 위해 중첩 루프를 사용하기 때문에 O(N^2)입니다.

공간 복잡도 - O(1) 왜냐하면 우리는 일정한 공간을 사용하기 때문입니다.

방법 2

이 방법에서는 위 방법의 코드를 최적화하여 솔루션의 시간 복잡도를 개선하겠습니다. 대문자는 +1로, 소문자는 -1로 처리됩니다. 또한, 접두어 합계의 빈도를 저장하기 위해 맵 데이터 구조를 사용할 것입니다. 접두사 합계가 0이거나 맵에 저장된 접두사 합계와 같다면 개수 값을 늘릴 수 있습니다.

알고리즘

• 정수를 키-값 쌍으로 포함하는 "합계" 맵을 정의하세요.

• 변수 'cnt'를 정의하고 0으로 초기화하여 소문자와 대문자가 동일한 하위 문자열의 총 개수를 저장합니다. 동시에 접두어와

를 저장하기 위해 변수 'current'를 정의합니다.

• 문자열 탐색을 시작하세요. 현재 문자가 대문자인 경우 '현재' 변수를 1만큼 늘립니다. 그렇지 않으면 '현재' 문자를 1씩 감소시킵니다.

• 'current' 값이 0이면 하위 문자열을 찾아 'cnt' 값을 1

늘립니다.

• 지도에 "current"가 키로 포함되어 있는지 확인하세요. 그렇다면 해당 값을 가져와 "cnt" 변수에 추가합니다.

• 지도의 "현재" 키 값을 1만큼 늘립니다.

Example

Example

문제를 더 잘 이해하기 위해. 예제 입력인 'TutOR'을 디버깅해 보겠습니다.

따라서 문자열 반복을 시작하면 첫 번째 인덱스에서 'current' 값이 0이 됩니다. 따라서 'cnt'의 값을 1만큼 늘립니다. 다시 말하지만, 세 번째 인덱스에서는 0이 됩니다. 따라서 'cnt' 값을 1 증가시켜 2가 되도록 합니다. 이전에도 0을 얻었으므로 맵에 존재하므로 해당 값을 'cnt'에 추가해야 합니다. 따라서 3이 됩니다.

4번째 인덱스에 도달하면 '현재' 변수의 값은 1이 되며 0번째 인덱스에서 얻은 것처럼 다시 가져옵니다. 따라서 'cnt'에 '1'을 추가합니다.

기본 논리는 '현재'가 0이면 하위 문자열을 얻는 것입니다. 'current' 값을 다시 얻으면 'current - current'가 0이므로 두 인덱스 사이의 문자열을 얻을 수 있습니다.

출력

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

공간 복잡성 – O(N) 왜냐하면 우리는 접두어 합계를 저장하기 위해 맵을 사용하기 때문입니다. 최악의 경우 문자열에 소문자 또는 대문자가 모두 포함되어 있으면 O(N) 공간이 필요합니다.

위 문제를 해결하기 위해 두 가지 다른 방법을 사용하는 방법을 배웠습니다. 첫 번째 방법은 중첩 루프를 사용하여 모든 문자열을 확인하는 반면, 두 번째 방법은 시간 복잡도 측면에서 첫 번째 방법보다 효율적이지만 더 많은 공간을 차지합니다.

위 내용은 소문자와 대문자의 수가 동일한 하위 문자열의 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!