Comptez le nombre de façons de diviser une chaîne en K sous-chaînes commençant par un nombre pair et ayant une longueur minimale de M

Dans ce problème, nous calculerons la manière de diviser la chaîne donnée en K sous-chaînes de telle sorte qu'elle satisfasse aux conditions données dans l'énoncé du problème.

Nous utiliserons la récursivité pour résoudre ce problème. De plus, nous utiliserons des méthodes de programmation dynamique tabulaire pour résoudre efficacement ce problème.

Énoncé du problème - Nous avons une chaîne de longueur spécifique appelée bin_Str. La chaîne contient uniquement des caractères numériques de « 0 » à « 9 ». Nous devons calculer le nombre de façons de diviser la chaîne en K sous-chaînes afin qu'elle remplisse les conditions suivantes.

• La sous-chaîne doit contenir au moins 2 caractères.

• Le premier caractère de chaque sous-chaîne doit être pair et le dernier caractère doit être impair.

Exemple Exemple

Entrez

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

Sortie

1

Explication − Sur la base des conditions de l'énoncé du problème, nous pouvons diviser 255 | 687 en parties de la chaîne donnée.

Entrez

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

Sortie

0

Explication - Puisque la chaîne ne contient que des nombres pairs, nous ne pouvons pas la diviser en deux sous-chaînes de telle sorte que chaque sous-chaîne se termine par un nombre impair.

Entrez

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

Sortie

3

Explication - Les méthodes de partitionnement possibles sont 85|65|49867, 8565|49|867 et 85|6549|867.

Méthode 1

Nous utiliserons une fonction récursive pour résoudre ce problème. Si nous trouvons une sous-chaîne valide à l'index actuel, nous effectuons un appel récursif comptant le nombre de façons de diviser la sous-chaîne restante en K - 1 sous-chaînes.

Algorithme

Étape 1 − Obtenez le premier et le dernier caractère de la chaîne donnée.

Étape 2 − Si le premier caractère n'est pas pair et que le dernier caractère n'est pas impair, renvoyez 0.

Étape 3 − Si l'index de départ est égal à la longueur de la chaîne, renvoie 0 car nous avons atteint la fin de la chaîne donnée.

Étape 4− Si K == 1, prenez la différence entre la longueur de la chaîne et l'index de départ. S'il est égal ou supérieur à M, alors 1 est renvoyé. Sinon, renvoie 0. Ici, si K vaut 1, nous devons obtenir la sous-chaîne restante.

Étape 5 - Initialisez « ops » à « 0 » pour stocker le nombre de divisions, et « len » à « 0 » pour stocker la longueur de la sous-chaîne actuelle.

Étape 6 − Parcourez la chaîne en commençant par l'index "start" jusqu'à la fin de la chaîne.

Étape 7− Augmentez « len » de 1. En même temps, récupérez le personnage actuel et le personnage suivant.

Étape 8− Si 'len' est supérieur à M, et que le nombre actuel est impair et que le nombre suivant est pair, nous pouvons terminer la partition à l'index actuel. Alors, effectuez un appel récursif à la fonction countWays() en passant l'index suivant et K - 1 comme paramètres de fonction.

Étape 9− Enfin, renvoyez la valeur de « ops ».

Exemple

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

Sortie

The number of ways to split the string is 1

Le nombre de façons de diviser une chaîne est de 1

Complexité spatiale - O(1) puisque nous n'utilisons pas d'espace supplémentaire.

Méthode 2

Dans cette méthode, nous utiliserons la technique de programmation dynamique tabulaire pour compter le nombre de façons de diviser la chaîne en K parties. Nous utiliserons une matrice pour stocker la sortie de l’état précédent.

Algorithme

Étape 1 - Définissez un tableau matriciel global matrice[] de taille 1001 x 1001. Les lignes de la matrice correspondent à un caractère de chaîne et les colonnes de la matrice correspondent à K.

Étape 2 − Obtenez le premier et le dernier caractères de la chaîne. Si le premier caractère est pair et le dernier caractère impair, la fonction countWays() est exécutée. Sinon, imprimez 0 dans la sortie.

Étape 3 − Dans la fonction countWays, initialisez le tableau matrice[].

Étape 4 − Le nombre de lignes de la matrice parcourue est égal à la longueur de la chaîne, et le nombre de colonnes est égal à K. Si le nombre de lignes est égal à la longueur de la chaîne, mettez à jour la ligne entière à 0.

Étape 5 − Sinon, si q est 1 et que la longueur de la chaîne moins l'index actuel est supérieure à M, initialisez le tableau matrice[p][q] avec 1. Sinon, initialisez matrice[p][q] avec 0.

Étape 6 − Dans les autres cas, initialisez la matrice [p][q] à -1.

Étape 7− Remplissez la matrice à l'aide de deux boucles imbriquées. Utilisez une boucle externe pour parcourir de 2 à K et utilisez une boucle imbriquée pour parcourir de 0 à la longueur de la chaîne.

Étape 8 - Initialisez 'ops' et 'len' à 0. De plus, parcourez la chaîne en commençant au p-ième index et incrémentez « len » de 1 à chaque itération.

Étape 9 − Supprimez le caractère actuel et le caractère suivant de la chaîne.

Étape 10− Si la longueur est supérieure à M, le caractère actuel est impair et le caractère suivant est pair, ajoutez matrice[k + 1][q − 1] à 'ops'.

Étape 11− Utilisez « ops » pour mettre à jour la matrice [p][q].

Étape 12− Enfin, renvoyez la matrice[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)。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!