文字列を偶数から始まり最小長 M の K 個の部分文字列に分割する方法の数を数えます。

この問題では、問題文で指定された条件を満たすように、指定された文字列を K 個の部分文字列に分割する方法を計算します。

この問題を解決するには再帰を使用します。さらに、表形式の動的プログラミング手法を使用して、この問題を効率的に解決します。

問題ステートメント - bin_Str という特定の長さの文字列があります。文字列には「0」から「9」までの数字のみが含まれます。次の条件を満たすように、文字列を K 個の部分文字列に分割する方法の数を計算する必要があります。

• 部分文字列には少なくとも 2 文字が含まれている必要があります。

• 各部分文字列の最初の文字は偶数、最後の文字は奇数である必要があります。

例例

説明 - 問題ステートメントの条件に基づいて、255 | 687 を指定された文字列の部分に分割できます。

説明 -文字列には偶数のみが含まれているため、各部分文字列が奇数で終わるように文字列を 2 つの部分文字列に分割することはできません。

説明 -可能なパーティション分割方法は、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' に初期化します。

- 「開始」インデックスから文字列の終わりまで文字列をトラバースします。

- 「len」を 1 ずつ増やします。同時に、現在の文字と次の文字を取得します。

- 「len」が M より大きく、現在の数値が奇数で次の数値が偶数の場合、現在のインデックスでパーティションを終了できます。したがって、次のインデックスと K - 1 を関数の引数として渡して、 countWays() 関数への再帰呼び出しを行います。

- 最後に、「ops」の値を返します。 ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー 文字列を分割する方法の数は 1 です

スペースの複雑さ - 余分なスペースを使用しないため、O(1)。 方法 2

このメソッドでは、表形式の動的プログラミング手法を使用して、文字列を K 個の部分に分割する方法の数を計算します。行列を使用して、前の状態の出力を保存します。 ＃＃＃アルゴリズム＃＃＃

- サイズ 1001 x 1001 のグローバル行列行列 [] 配列を定義します。行列の行は文字列文字にマップされ、行列の列は K にマップされます。

- 文字列の最初と最後の文字を取得します。最初の文字が偶数で最後の文字が奇数の場合、countWays() 関数が実行されます。それ以外の場合は、出力に 0 を出力します。

- countWays 関数で、matrix[] 配列を初期化します。

- 走査された行列の行数は文字列の長さに等しく、列数は K に等しくなります。行数が文字列長と等しい場合は、行全体を 0 に更新します。

- それ以外の場合、q が 1 で、文字列の長さから現在のインデックスを引いた値が M より大きい場合は、配列行列 [p][q] を 1 で初期化します。それ以外の場合は、matrix[p][q] を 0 で初期化します。

- その他の場合は、行列 [p][q] を -1 に初期化します。

- 2 つのネストされたループを使用して行列を埋めます。外側のループを使用して 2 から K まで移動し、ネストされたループを使用して 0 から文字列の長さまで移動します。

- 'ops' と 'len' を 0 に初期化します。さらに、p 番目のインデックスから始まる文字列を反復し、反復ごとに 'len' を 1 ずつ増分します。

ステップ 9 - 文字列の現在の文字と次の文字を取り出します。

ステップ 10- 長さが M より大きく、現在の文字が奇数で、次の文字が偶数の場合は、matrix[k 1][q − 1] を 'ops' に追加します。

ステップ 11- 「ops」を使用して行列 [p][q] を更新します。

ステップ 12- 最後に行列 [0][k] を返します。

Example

示例

#include 
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 中国語 Web サイトの他の関連記事を参照してください。