문자열을 짝수로 시작하고 최소 길이가 M인 K개의 하위 문자열로 분할하는 방법의 수를 계산합니다.

이 문제에서는 문제 설명에 주어진 조건을 만족하도록 주어진 문자열을 K개의 하위 문자열로 나누는 방법을 계산합니다.

우리는 이 문제를 해결하기 위해 재귀를 사용할 것입니다. 또한 이 문제를 효율적으로 해결하기 위해 표 형식의 동적 프로그래밍 방법을 사용할 것입니다.

문제 설명 − bin_Str이라는 특정 길이의 문자열이 있습니다. 문자열에는 '0'부터 '9'까지의 숫자만 포함됩니다. 다음 조건을 충족하도록 문자열을 K개의 하위 문자열로 분할하는 방법의 수를 계산해야 합니다.

• 하위 문자열은 2자 이상이어야 합니다.

• 각 하위 문자열의 첫 번째 문자는 짝수여야 하고 마지막 문자는 홀수여야 합니다.

예제 예

들어가세요

으아아아

출력

으아아아

설명 − 문제 설명의 조건에 따라 255 | 687을 주어진 문자열의 일부로 나눌 수 있습니다.

들어가세요

으아아아

출력

으아아아

설명 − 문자열에는 짝수만 포함되어 있으므로 각 하위 문자열이 홀수로 끝나도록 문자열을 두 개의 하위 문자열로 분할할 수 없습니다.

들어가세요

으아아아

출력

으아아아

설명 − 가능한 파티셔닝 방법은 85|65|49867, 8565|49|867 및 85|6549|867입니다.

방법 1

우리는 이 문제를 해결하기 위해 재귀 함수를 사용할 것입니다. 현재 인덱스에서 유효한 하위 문자열을 찾으면 나머지 하위 문자열을 K - 1 하위 문자열로 분할하는 방법의 수를 계산하는 재귀 호출을 수행합니다.

알고리즘

1단계 − 주어진 문자열의 첫 번째 문자와 마지막 문자를 가져옵니다.

2단계 − 첫 번째 문자가 짝수가 아니고 마지막 문자가 홀수가 아니면 0을 반환합니다.

3단계 − 시작 인덱스가 문자열 길이와 같으면 주어진 문자열의 끝에 도달했기 때문에 0이 반환됩니다.

4단계− K == 1이면 문자열 길이와 시작 인덱스의 차이를 구합니다. M보다 크거나 같으면 1이 반환됩니다. 그렇지 않으면 0을 반환합니다. 여기서 K가 1이면 나머지 부분 문자열을 가져와야 합니다.

5단계 - 분할 횟수를 저장하려면 'ops'를 '0'으로 초기화하고, 현재 하위 문자열의 길이를 저장하려면 'len'을 '0'으로 초기화하세요.

6단계 − "시작" 인덱스부터 문자열 끝까지 문자열을 탐색합니다.

7단계− 'len'을 1만큼 늘립니다. 동시에 현재 문자와 다음 문자를 가져옵니다.

8단계− 'len'이 M보다 크고 현재 숫자가 홀수이고 다음 숫자가 짝수이면 현재 인덱스에서 파티션을 종료할 수 있습니다. 따라서 다음 인덱스와 K - 1을 함수 인수로 전달하여 countWays() 함수에 대한 재귀 호출을 수행합니다.

9단계− 마지막으로 'ops' 값을 반환합니다.

예

으아아아

출력

으아아아

문자열을 나누는 방법의 수는 1

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

방법 2

이 방법에서는 테이블 형식 동적 프로그래밍 기술을 사용하여 문자열을 K 부분으로 분할하는 방법의 수를 계산합니다. 이전 상태의 출력을 저장하기 위해 행렬을 사용할 것입니다.

알고리즘

1단계 - 크기가 1001 x 1001인 전역 행렬 행렬[] 배열을 정의합니다. 행렬의 행은 문자열 문자에 매핑되고 행렬의 열은 K에 매핑됩니다.

2단계 − 문자열의 첫 번째 문자와 마지막 문자를 가져옵니다. 첫 번째 문자가 짝수이고 마지막 문자가 홀수이면 countWays() 함수가 실행됩니다. 그렇지 않으면 출력에 0을 인쇄합니다.

3단계 − countWays 함수에서 행렬[] 배열을 초기화합니다.

4단계 − 순회된 행렬의 행 수는 문자열 길이와 같고, 열 수는 K와 같습니다. 행 수가 문자열 길이와 같으면 전체 행을 0으로 업데이트합니다.

5단계 − 그렇지 않고 q가 1이고 문자열 길이에서 현재 인덱스를 뺀 값이 M보다 큰 경우 배열 행렬[p][q]를 1로 초기화합니다. 그렇지 않으면 행렬[p][q]를 0으로 초기화합니다.

6단계 − 다른 경우에는 행렬 [p][q]를 -1로 초기화합니다.

7단계− 두 개의 중첩 루프를 사용하여 행렬을 채웁니다. 2에서 K로 이동하려면 외부 루프를 사용하고, 0에서 문자열 길이까지 이동하려면 중첩 루프를 사용합니다.

8단계 - 'ops' 및 'len'을 0으로 초기화합니다. 또한 p번째 인덱스부터 시작하여 문자열을 반복하고 각 반복마다 'len'을 1씩 증가시킵니다.

9단계 − 문자열의 현재 문자와 다음 문자를 꺼냅니다.

10단계− 길이가 M보다 크고 현재 문자가 홀수이고 다음 문자가 짝수인 경우 'ops'에 행렬[k + 1][q − 1]을 추가합니다.

11단계− 행렬 [p][q]를 업데이트하려면 'ops'를 사용하세요.

12단계− 마지막으로 행렬[0][k]을 반환합니다.

Example

的中文翻译为：

示例

#include <bits/stdc++.h>
using namespace std;

int matrix[1001][1001];
int countWays(int str_len, int K, int M, string bin_str) {
    // Base case
    for (int p = 0; p <= str_len; p++) {
        for (int q = 0; q <= K; q++) {
            // When index points to end index of string
            if (p == str_len)
                matrix[p][q] = 0;
            else if (q == 1) {
                // When only 1 split needs to be done
                int chars = str_len - p;
                // Validating substring's minimum len
                if (chars >= M)
                    matrix[p][q] = 1;
                else
                    matrix[p][q] = 0;
            } else {
                // For other cases
                matrix[p][q] = -1;
            }
        }
    }
    // Dynamic programming approach
    for (int q = 2; q <= K; q++) {
        for (int p = 0; p < str_len; p++) {
            int ops = 0;
            int len = 0; // length of current substring
            for (int k = p; k < str_len - 1; k++) {
                len++;
                int first = bin_str[k] - '0';
                int second = bin_str[k + 1] - '0';
                // Validate condition for split
                if (len >= M && first % 2 == 1 && second % 2 == 0) {
                    // Substring starting from k + 1 index needs to be splited in q-1 parts
                    ops += matrix[k + 1][q - 1];
                }
            }
            matrix[p][q] = ops;
        }
    }
    return matrix[0][K];
}
int main() {
    int M = 2, K = 2;
    string bin_str = "255687";
    int str_len = bin_str.length();
    int f_char = bin_str[0] - '0';
    int l_char = bin_str[str_len - 1] - '0';
    cout << "The number of ways to split the string is ";
    if (f_char % 2 != 0 || l_char % 2 != 1) {
        cout << 0 << endl;
    } else {
        cout << countWays(str_len, K, M, bin_str) << endl;
    }
    return 0;
}

输出

The number of ways to split the string is 1

时间复杂度 - O(N*N*K)，其中 O(N*N) 用于找到所有子字符串，O(K) 用于 K 个分区。

空间复杂度 - 使用matrix[]数组为O(N*K)。

위 내용은 문자열을 짝수로 시작하고 최소 길이가 M인 K개의 하위 문자열로 분할하는 방법의 수를 계산합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!