計算將字串分割為以偶數開頭且最小長度為M的K個子字串的方法數

在這個問題中，我們將計算給定的字串分成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’的值。

Example

#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]。

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中文網其他相關文章！