在這個問題中，我們將計算給定的字串分成K個子字串的方法，使其滿足問題陳述中給出的條件。
我們將使用遞歸來解決這個問題。此外，我們還將使用表格動態規劃方法來有效解決這個問題。
問題陳述 − 我們有一個名為bin_Str的特定長度的字串。該字串只包含從'0'到'9'的數字字元。我們需要計算將字串分割成K個子字串的方式數，使其滿足以下條件。
子字串應至少包含2個字元。
每個子字串的第一個字元應為偶數，最後一個字元應為奇數。
範例範例
輸入
M = 2, K = 2; bin_str = "255687"
Output
#1
Explanation − 根據問題陳述的條件，我們可以將255 | 687分割成給定字串的一部分。
輸入
M = 2, K = 2; bin_str = "26862";
Output
#0
解釋 − 由於字串只包含偶數數字，我們無法將其分割成兩個子字串，使得每個子字串以奇數數字結尾。
輸入
M = 2, K = 3; bin_str = "856549867";
輸出
3
Explanation − 可能的分割方式有85|65|49867、8565|49|867和85|6549|867。
我們將使用遞歸函數來解決這個問題。如果我們在當前索引中找到了有效的子字串，我們會進行遞歸調用，計算將剩餘子字串分成 K - 1 個子字串的方法數量。
步驟 1 − 取給定字串的第一個和最後一個字元。
步驟 2 − 如果第一個字元不是偶數，且最後一個字元不是奇數，則傳回 0。
步驟 3 − 如果起始索引等於字串長度，則傳回 0，因為我們已經到達給定字串的末端。
第4步− 如果 K == 1，則取字串長度與起始索引之間的差值。如果它等於或大於 M，則傳回 1。否則，返回 0。在這裡，如果 K 為 1，我們需要取得剩餘的子字串。
步驟5 - 將‘ops’初始化為‘0’，以儲存分割方式的計數，將‘len’初始化為‘0’，以儲存目前子字串的長度。
步驟 6 − 從「start」索引開始遍歷字串直到字串的結尾。
第7步− 將‘len’增加1。同時，取得目前字元和下一個字元。
第8步− 如果'len'大於M，且目前數字是奇數，下一個數字是偶數，我們可以在目前索引處結束分區。因此，透過將下一個索引和K - 1作為函數參數傳遞，對countWays()函數進行遞歸呼叫。
第9步− 最後，傳回‘ops’的值。
#include <bits/stdc++.h>
using namespace std;
int countWays(int start, int str_len, int K, int M, string bin_str) {
// Geeting first and last character of the substring
int f_char = bin_str[0] - '0';
int l_char = bin_str[str_len - 1] - '0';
if (f_char % 2 != 0 || l_char % 2 != 1) {
return 0;
}
// When we reach at the end
if (start == str_len)
return 0;
// Base case
if (K == 1) {
int chars = str_len - start;
// Validate minimum length of substring
if (chars >= M)
return 1;
return 0;
}
int ops = 0;
int len = 0;
// Traverse all partions
for (int p = start; p < str_len - 1; p++) {
len++;
int first = bin_str[p] - '0';
int second = bin_str[p + 1] - '0';
// If we can end the partition at p and start a new partition at p+1
if (len >= M && first % 2 == 1) {
if (second % 2 == 0) {
ops += countWays(p + 1, str_len, K - 1, M, bin_str);
}
}
}
return ops;
}
int main() {
int M = 2, K = 2;
string bin_str = "255687";
int str_len = bin_str.length();
cout << "The number of ways to split the string is " << countWays(0, str_len, K, M, bin_str) << endl;
return 0;
}
The number of ways to split the string is 1
將字串分割的方式數量為1
空間複雜度 - O(1)，因為我們不使用額外的空間。
在這個方法中，我們將使用表格動態規劃技術來計算將字串分割成K個部分的方法數。我們將使用矩陣來儲存先前狀態的輸出。
步驟 1 - 定義大小為 1001 x 1001 的全域矩陣 matrix[] 陣列。矩陣的行映射到一個字串字符，矩陣的列映射到 K。
第二步 − 取字串的第一個和最後一個字元。如果第一個字元是偶數且最後一個字元是奇數，則執行countWays()函數。否則，在輸出中列印0。
步驟 3 − 在 countWays 函數中，初始化 matrix[] 陣列。
步驟 4 − 遍歷矩陣的行數等於字串長度，列數等於K。如果行數等於字串長度，則將整行更新為0。
步驟5 − 否則，如果q為1，且字串長度減去目前索引大於M，則用1初始化陣列matrix[p][q]。否則，用0初始化matrix[p][q]。
步驟 6 − 在其他情況下，將矩陣[p][q]初始化為-1。
第7步− 使用兩個巢狀迴圈填入矩陣。使用外部循環進行2到K的遍歷，使用巢狀循環進行0到字串長度的遍歷。
第8步 - 將'ops'和'len'初始化為0。此外，從第p個索引開始遍歷字串，並在每次迭代中將'len'增加1。
步驟9 − 取出字串的目前字元和下一個字元。
第10步− 如果長度大於M，當前字元是奇數，且下一個字元是偶數，則將matrix[k 1][q − 1]加到'ops'中。
第11步− 使用‘ops’更新矩陣[p][q]。
第12步− 最後回傳matrix[0][k]。
#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中文網其他相關文章！
