Zählen Sie die Anzahl der Möglichkeiten, eine Zeichenfolge in K Teilzeichenfolgen aufzuteilen, beginnend mit einer geraden Zahl und einer Mindestlänge von M

In diesem Problem berechnen wir, wie wir die gegebene Zeichenfolge in K Teilzeichenfolgen aufteilen, sodass sie die in der Problemstellung angegebenen Bedingungen erfüllt.

Wir werden Rekursion verwenden, um dieses Problem zu lösen. Darüber hinaus werden wir tabellarische dynamische Programmiermethoden verwenden, um dieses Problem effizient zu lösen.

Problemstellung − Wir haben eine Zeichenfolge mit einer bestimmten Länge namens bin_Str. Die Zeichenfolge enthält nur numerische Zeichen von „0“ bis „9“. Wir müssen die Anzahl der Möglichkeiten berechnen, die Zeichenfolge in K Teilzeichenfolgen aufzuteilen, sodass sie die folgenden Bedingungen erfüllt.

• Substring sollte mindestens 2 Zeichen enthalten.

• Das erste Zeichen jedes Teilstrings sollte gerade und das letzte Zeichen ungerade sein.

Beispiel Beispiel

Eintreten

M = 2, K = 2; bin_str = "255687"

Ausgabe

1

Erläuterung − Basierend auf den Bedingungen der Problemstellung können wir 255 | 687 in Teile der angegebenen Zeichenfolge aufteilen.

Eintreten

M = 2, K = 2; bin_str = "26862";

Ausgabe

0

Erläuterung − Da die Zeichenfolge nur gerade Zahlen enthält, können wir sie nicht in zwei Teilzeichenfolgen aufteilen, sodass jede Teilzeichenfolge mit einer ungeraden Zahl endet.

Eintreten

M = 2, K = 3; bin_str = "856549867";

Ausgabe

3

Erklärung − Mögliche Partitionierungsmethoden sind 85|65|49867, 8565|49|867 und 85|6549|867.

Methode 1

Wir werden eine rekursive Funktion verwenden, um dieses Problem zu lösen. Wenn wir am aktuellen Index einen gültigen Teilstring finden, führen wir einen rekursiven Aufruf durch und zählen die Anzahl der Möglichkeiten, den verbleibenden Teilstring in K – 1 Teilstrings aufzuteilen.

Algorithmus

Schritt 1 − Holen Sie sich das erste und letzte Zeichen der angegebenen Zeichenfolge.

Schritt 2 − Wenn das erste Zeichen nicht gerade und das letzte Zeichen nicht ungerade ist, geben Sie 0 zurück.

Schritt 3 − Wenn der Startindex gleich der Stringlänge ist, geben Sie 0 zurück, da wir das Ende des angegebenen Strings erreicht haben.

Schritt 4− Wenn K == 1, nehmen Sie die Differenz zwischen der Stringlänge und dem Startindex. Wenn es gleich oder größer als M ist, wird 1 zurückgegeben. Andernfalls wird 0 zurückgegeben. Wenn K hier 1 ist, müssen wir den verbleibenden Teilstring abrufen.

Schritt 5 – Initialisieren Sie „ops“ auf „0“, um die Anzahl der Teilungen zu speichern, und „len“ auf „0“, um die Länge des aktuellen Teilstrings zu speichern.

Schritt 6 − Durchlaufen Sie die Zeichenfolge beginnend vom „Start“-Index bis zum Ende der Zeichenfolge.

Schritt 7− Erhöhen Sie „len“ um 1. Rufen Sie gleichzeitig das aktuelle und das nächste Zeichen ab.

Schritt 8− Wenn „len“ größer als M ist und die aktuelle Zahl ungerade und die nächste Zahl gerade ist, können wir die Partition am aktuellen Index beenden. Führen Sie also einen rekursiven Aufruf der Funktion countWays() durch, indem Sie den nächsten Index und K - 1 als Funktionsargumente übergeben.

Schritt 9− Geben Sie abschließend den Wert von „ops“ zurück.

Beispiel

#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;
}

Ausgabe

The number of ways to split the string is 1

Es gibt 1 Möglichkeiten, eine Zeichenfolge zu teilen

Raumkomplexität – O(1), da wir keinen zusätzlichen Raum verbrauchen.

Methode 2

Bei dieser Methode verwenden wir eine tabellarische dynamische Programmiertechnik, um die Anzahl der Möglichkeiten zu zählen, die Zeichenfolge in K Teile aufzuteilen. Wir werden eine Matrix verwenden, um die Ausgabe des vorherigen Zustands zu speichern.

Algorithmus

Schritt 1 – Definieren Sie ein globales Matrixmatrix[]-Array mit der Größe 1001 x 1001. Die Zeilen der Matrix werden einem Zeichenfolgezeichen zugeordnet und die Spalten der Matrix werden K zugeordnet.

Schritt 2 − Holen Sie sich das erste und das letzte Zeichen der Zeichenfolge. Wenn das erste Zeichen gerade und das letzte Zeichen ungerade ist, wird die Funktion countWays() ausgeführt. Andernfalls geben Sie 0 in der Ausgabe aus.

Schritt 3 − Initialisieren Sie in der countWays-Funktion das Matrix[]-Array.

Schritt 4 − Die Anzahl der Zeilen der durchlaufenen Matrix entspricht der Länge der Zeichenfolge und die Anzahl der Spalten entspricht K. Wenn die Anzahl der Zeilen der Länge der Zeichenfolge entspricht, aktualisieren Sie die gesamte Zeile auf 0.

Schritt 5 − Andernfalls, wenn q 1 ist und die Stringlänge minus dem aktuellen Index größer als M ist, initialisieren Sie das Array Matrix[p][q] mit 1. Andernfalls initialisieren Sie Matrix[p][q] mit 0.

Schritt 6 − In anderen Fällen initialisieren Sie die Matrix [p][q] auf -1.

Schritt 7− Füllen Sie die Matrix mit zwei verschachtelten Schleifen. Verwenden Sie eine äußere Schleife, um von 2 bis K zu durchlaufen, und verwenden Sie eine verschachtelte Schleife, um von 0 bis zur Länge der Zeichenfolge zu durchlaufen.

Schritt 8 – Initialisieren Sie „ops“ und „len“ auf 0. Darüber hinaus iterieren Sie über die Zeichenfolge, beginnend beim p-ten Index, und erhöhen Sie „len“ bei jeder Iteration um 1.

Schritt 9 − Nehmen Sie das aktuelle Zeichen und das nächste Zeichen der Zeichenfolge heraus.

Schritt 10− Wenn die Länge größer als M ist, das aktuelle Zeichen ungerade und das nächste Zeichen gerade ist, fügen Sie Matrix[k + 1][q − 1] zu „ops“ hinzu.

Schritt 11− Verwenden Sie „ops“, um die Matrix [p][q] zu aktualisieren.

Schritt 12− Zum Schluss Matrix[0][k] zurückgeben.

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)。

Das obige ist der detaillierte Inhalt vonZählen Sie die Anzahl der Möglichkeiten, eine Zeichenfolge in K Teilzeichenfolgen aufzuteilen, beginnend mit einer geraden Zahl und einer Mindestlänge von M. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!