Dada una string S de tamaño N que consta de dígitos y ? , la tarea es encontrar el número de strings formadas de manera que se reemplace el carácter ‘?’ con cualquier dígito tal que los dígitos de la string se vuelvan no decrecientes.
Ejemplos:
Entrada: S = “1???2”
Salida: 4
Explicación:
La string después de reemplazos válidos de ‘?’ es 11112, 11122, 11222, 12222. Por lo tanto, el recuento de dicha string es 1.Entrada: S = “2??43?4”
Salida: 0
Enfoque: El problema dado se puede resolver reemplazando ‘?’ con todas las posibles combinaciones válidas de dígitos usando recursividad y almacene los subproblemas superpuestos en la tabla dp[] . Siga los pasos a continuación para resolver el problema dado:
- Inicialice una array 2D , digamos dp[][] tal que dp[i][j] indicará el número posible de strings válidas que tienen la longitud i y entre dos números cuya diferencia de punto final es j . Como los diferentes segmentos que contienen ? son independientes entre si. Entonces, el conteo total será el producto de todas las opciones disponibles para cada segmento.
- Inicialice el dp[][] como -1.
- Declare tres variables L como 0 , R como 9 , cnt , de modo que L denote el límite izquierdo del segmento, R denote el límite derecho del segmento y cnt denote la longitud de ‘?’ contiguos. caracteres.
- Deje que el recuento total se almacene en la variable, digamos ans as 1 .
- Defina una función solve que calculará los valores de los Nodes dp recursivamente . La función de resolución tomará dos argumentos (len, gap) , len denotará la longitud total de continuo ‘?’ y la brecha denotará la diferencia entre los puntos finales de ese segmento como:
- Iterar para cada espacio posible y volver a calcular la respuesta con solve(len – 1, gap – i) .
- Devuelve la respuesta obtenida de la función de resolución después de llenar el Node dp[len][gap] .
- Repita cada carácter de la string y realice los siguientes pasos:
- Si el carácter actual es ‘?’ luego incrementa la variable cnt .
- Si el carácter actual no es un número, cambie el límite derecho, es decir, R al carácter actual, es decir, R = S[i] – ‘0’ .
- Multiplique la respuesta calculada por la función recursiva solve(cnt, R – L) .
- Después de completar los pasos anteriores, imprima el valor de ans como el conteo resultante de strings formadas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
// Define the dp table globally
int dp[MAXN][10];
// Recursive function to calculate total
// number of valid non-decreasing strings
int solve(int len, int gap)
{
// If already calculated state
if (dp[len][gap] != -1) {
return dp[len][gap];
}
// Base Case
if (len == 0 || gap == 0) {
return 1;
}
if (gap < 0) {
return 0;
}
// Stores the total count of strings
// formed
int ans = 0;
for (int i = 0; i <= gap; i++) {
ans += solve(len - 1, gap - i);
}
// Fill the value in dp matrix
return dp[len][gap] = ans;
}
// Function to find the total number of
// non-decreasing string formed by
// replacing the '?'
int countValidStrings(string S)
{
// Initialize all value of dp
// table with -1
memset(dp, -1, sizeof(dp));
int N = S.length();
// Left and Right limits
int L = 1, R = 9;
int cnt = 0;
int ans = 1;
// Iterate through all the characters
// of the string S
for (int i = 0; i < N; i++) {
if (S[i] != '?') {
// Change R to the current
// character
R = S[i] - '0';
// Call the recursive function
ans *= solve(cnt, R - L);
// Change L to R and R to 9
L = R;
R = 9;
// Reinitialize the length
// of ? to 0
cnt = 0;
}
else {
// Increment the length of
// the segment
cnt++;
}
}
// Update the ans
ans *= solve(cnt, R - L);
// Return the total count
return ans;
}
// Driver Code
int main()
{
string S = "1???2";
cout << countValidStrings(S);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
static final int MAXN = 100005;
// Define the dp table globally
static final int dp[][] = new int[MAXN][10];
// Recursive function to calculate total
// number of valid non-decreasing strings
static int solve(int len, int gap)
{
// If already calculated state
if (dp[len][gap] != -1) {
return dp[len][gap];
}
// Base Case
if (len == 0 || gap == 0) {
return 1;
}
if (gap < 0) {
return 0;
}
// Stores the total count of strings
// formed
int ans = 0;
for (int i = 0; i <= gap; i++) {
ans += solve(len - 1, gap - i);
}
// Fill the value in dp matrix
return dp[len][gap] = ans;
}
// Function to find the total number of
// non-decreasing string formed by
// replacing the '?'
static int countValidStrings(String S)
{
// Initialize all value of dp
// table with -1
for (int i = 0; i < MAXN; i++) {
for (int j = 0; j < 10; j++) {
dp[i][j] = -1;
}
}
int N = S.length();
// Left and Right limits
int L = 1, R = 9;
int cnt = 0;
int ans = 1;
// Iterate through all the characters
// of the string S
for (int i = 0; i < N; i++) {
if (S.charAt(i) != '?') {
// Change R to the current
// character
R = S.charAt(i) - '0';
// Call the recursive function
ans *= solve(cnt, R - L);
// Change L to R and R to 9
L = R;
R = 9;
// Reinitialize the length
// of ? to 0
cnt = 0;
}
else {
// Increment the length of
// the segment
cnt++;
}
}
// Update the ans
ans *= solve(cnt, R - L);
// Return the total count
return ans;
}
// Driver Code
public static void main(String[] args)
{
String S = "1???2";
System.out.println(countValidStrings(S));
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python 3 program for the above approach
MAXN = 100005
# Define the dp table globally
dp = [[-1 for x in range(10)] for y in range(MAXN)]
# Recursive function to calculate total
# number of valid non-decreasing strings
def solve(len, gap):
# If already calculated state
if (dp[len][gap] != -1):
return dp[len][gap]
# Base Case
if (len == 0 or gap == 0):
return 1
if (gap < 0):
return 0
# Stores the total count of strings
# formed
ans = 0
for i in range(gap + 1):
ans += solve(len - 1, gap - i)
# Fill the value in dp matrix
dp[len][gap] = ans
return dp[len][gap]
# Function to find the total number of
# non-decreasing string formed by
# replacing the '?'
def countValidStrings(S):
# Initialize all value of dp
# table with -1
global dp
N = len(S)
# Left and Right limits
L, R = 1, 9
cnt = 0
ans = 1
# Iterate through all the characters
# of the string S
for i in range(N):
if (S[i] != '?'):
# Change R to the current
# character
R = ord(S[i]) - ord('0')
# Call the recursive function
ans *= solve(cnt, R - L)
# Change L to R and R to 9
L = R
R = 9
# Reinitialize the length
# of ? to 0
cnt = 0
else:
# Increment the length of
# the segment
cnt += 1
# Update the ans
ans *= solve(cnt, R - L)
# Return the total count
return ans
# Driver Code
if __name__ == "__main__":
S = "1???2"
print(countValidStrings(S))
# This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
static int MAXN = 100005;
// Define the dp table globally
static int [,]dp = new int[MAXN, 10];
// Recursive function to calculate total
// number of valid non-decreasing strings
static int solve(int len, int gap)
{
// If already calculated state
if (dp[len,gap] != -1) {
return dp[len,gap];
}
// Base Case
if (len == 0 || gap == 0) {
return 1;
}
if (gap < 0) {
return 0;
}
// Stores the total count of strings
// formed
int ans = 0;
for (int i = 0; i <= gap; i++) {
ans += solve(len - 1, gap - i);
}
// Fill the value in dp matrix
return dp[len,gap] = ans;
}
// Function to find the total number of
// non-decreasing string formed by
// replacing the '?'
static int countValidStrings(string S)
{
// Initialize all value of dp
// table with -1
for(int i = 0; i < MAXN; i++){
for(int j = 0; j < 10; j++){
dp[i, j] = -1;
}
}
int N = S.Length;
// Left and Right limits
int L = 1, R = 9;
int cnt = 0;
int ans = 1;
// Iterate through all the characters
// of the string S
for (int i = 0; i < N; i++) {
if (S[i] != '?') {
// Change R to the current
// character
R = (int)S[i] - 48;
// Call the recursive function
ans *= solve(cnt, R - L);
// Change L to R and R to 9
L = R;
R = 9;
// Reinitialize the length
// of ? to 0
cnt = 0;
}
else {
// Increment the length of
// the segment
cnt++;
}
}
// Update the ans
ans *= solve(cnt, R - L);
// Return the total count
return ans;
}
// Driver Code
public static void Main()
{
string S = "1???2";
Console.Write(countValidStrings(S));
}
}
// This code is contributed by SURENDR_GANGWAR.
Javascript
<script>
// JavaScript Program to implement
// the above approach
let MAXN = 100005
// Define the dp table globally
let dp = new Array(MAXN).fill(new Array(10));
// Recursive function to calculate total
// number of valid non-decreasing strings
function solve(len, gap)
{
// If already calculated state
if (dp[len][gap] != -1) {
return dp[len][gap];
}
// Base Case
if (len == 0 || gap == 0) {
return 1;
}
if (gap < 0) {
return 0;
}
// Stores the total count of strings
// formed
let ans = 0;
for (let i = 0; i <= gap; i++) {
ans += solve(len - 1, gap - i);
}
// Fill the value in dp matrix
return dp[len][gap] = ans;
}
// Function to find the total number of
// non-decreasing string formed by
// replacing the '?'
function countValidStrings(S)
{
// Initialize all value of dp
// table with -1
for (let i = 0; i < dp.length; i++) {
for (let j = 0; j < dp[i].length; j++) {
dp[i][j] = -1;
}
}
let N = S.length;
// Left and Right limits
let L = 1, R = 9;
let cnt = 0;
let ans = 1;
// Iterate through all the characters
// of the string S
for (let i = 0; i < N; i++) {
if (S[i] != '?') {
// Change R to the current
// character
R = S.charCodeAt(i) - '0'.charCodeAt(0);
// Call the recursive function
ans *= solve(cnt, R - L);
// Change L to R and R to 9
L = R;
R = 9;
// Reinitialize the length
// of ? to 0
cnt = 0;
}
else {
// Increment the length of
// the segment
cnt++;
}
}
// Update the ans
ans *= solve(cnt, R - L);
// Return the total count
return ans;
}
// Driver Code
let S = "1???2";
document.write(countValidStrings(S));
// This code is contributed by Potta Lokesh
</script>
Producción:
4
Complejidad de Tiempo: O(N*10)
Espacio Auxiliar: O(N*10)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA