Dada una string numérica S que consta de solo tres tipos de caracteres 0, 1 y 2 inicialmente y después de dos operaciones:
- La ocurrencia de dos 1 consecutivos puede ser reemplazada por 3.
- La ocurrencia de dos 2 consecutivos puede ser reemplazada por 4.
La tarea dada es encontrar el número total de strings diferentes que se pueden formar usando las operaciones.
Ejemplos:
Entrada: S = “0110000022”
Salida: 4
Explicación:
Puede haber cuatro formas diferentes usando las operaciones, las cuatro strings son
“0110000022”, “030000022”, “03000004”, “011000004”
Entrada: S = “111”
Salida : 3
Enfoque:
Para resolver este problema, estamos utilizando un enfoque de programación dinámica. Definimos un arreglo dp para almacenar el conteo de posibles strings de longitud igual a sus respectivos índices.
- Inicializar dp[0] = dp[1] = 1.
- Para cualquier índice i entre [1, N-1] , si el carácter en ese índice es ‘1’ o ‘2’ y es igual al de su índice anterior, agregue las posibles strings que se pueden formar de longitud i-1 y i-2 . De lo contrario, es el mismo que el de la longitud i-1 .
dp[i + 1] = dp[i] + dp[i-1] si S[i] == S[i-1] donde S[i] es ‘1’ o ‘2’.
dp[i + 1] = dp[i] en caso contrario.
- Retorna dp[n] como el conteo de diferentes strings posibles.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include
using namespace std;
// Function that prints the
// number of different strings
// that can be formed
void differentStrings(string s)
{
// Computing the length of
// the given string
int n = s.length();
vector dp(n + 1);
// Base case
dp[0] = dp[1] = 1;
// Traverse the given string
for (int i = 1; i < n; i++) {
// If two consecutive 1's
// or 2's are present
if (s[i] == s[i - 1]
&& (s[i] == '1'
|| s[i] == '2'))
dp[i + 1]
= dp[i] + dp[i - 1];
// Otherwise take
// the previous value
else
dp[i + 1] = dp[i];
}
cout << dp[n] << "\n";
}
// Driver Code
int main()
{
string S = "0111022110";
differentStrings(S);
return 0;
}
C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void differentStrings(char* s)
{
// Computing the length of
// the given string
int n = strlen(s);
int dp[n + 1];
// Base case
dp[0] = dp[1] = 1;
// Traverse the given string
for (int i = 1; i < n; i++) {
// If two consecutive 1's
// or 2's are present
if (s[i] == s[i - 1]
&& (s[i] == '1'
|| s[i] == '2'))
dp[i + 1] = dp[i] + dp[i - 1];
// Otherwise take
// the previous value
else
dp[i + 1] = dp[i];
}
printf("%d\n", dp[n]);
}
// Driver Code
int main()
{
char S[] = "0111022110";
differentStrings(S);
return 0;
}
// This code is contributed by phalashi.
Java
// Java implementation of the above approach
import java.io.*;
class GFG{
// Function that prints the
// number of different strings
// that can be formed
static void differentStrings(String s)
{
// Computing the length of
// the given string
int n = s.length();
int[] dp = new int[n + 1];
// Base case
dp[0] = dp[1] = 1;
// Traverse the given string
for(int i = 1; i < n; i++)
{
// If two consecutive 1's
// or 2's are present
if (s.charAt(i) == s.charAt(i - 1) &&
(s.charAt(i) == '1' ||
s.charAt(i) == '2'))
dp[i + 1] = dp[i] + dp[i - 1];
// Otherwise take the
// previous value
else
dp[i + 1] = dp[i];
}
System.out.println(dp[n]);
}
// Driver code
public static void main(String[] args)
{
String S = "0111022110";
differentStrings(S);
}
}
// This code is contributed by offbeat
Python3
# Python3 implementation of # the above approach # Function that prints the # number of different strings # that can be formed def differentStrings(s): # Computing the length of # the given string n = len(s) dp = [0] * (n + 1) # Base case dp[0] = dp[1] = 1 # Traverse the given string for i in range (1, n): # If two consecutive 1's # or 2's are present if (s[i] == s[i - 1] and (s[i] == '1' or s[i] == '2')): dp[i + 1] = dp[i] + dp[i - 1] # Otherwise take # the previous value else: dp[i + 1] = dp[i] print (dp[n]) # Driver Code if __name__ == "__main__": S = "0111022110" differentStrings(S) # This code is contributed by Chitranayal
C#
// C# implementation of the above approach
using System;
class GFG{
// Function that prints the
// number of different strings
// that can be formed
static void differentStrings(string s)
{
// Computing the length of
// the given string
int n = s.Length;
int[] dp = new int[n + 1];
// Base case
dp[0] = dp[1] = 1;
// Traverse the given string
for(int i = 1; i < n; i++)
{
// If two consecutive 1's
// or 2's are present
if (s[i] == s[i - 1] &&
(s[i] == '1' ||
s[i] == '2'))
dp[i + 1] = dp[i] + dp[i - 1];
// Otherwise take the
// previous value
else
dp[i + 1] = dp[i];
}
Console.Write(dp[n]);
}
// Driver code
public static void Main()
{
string S = "0111022110";
differentStrings(S);
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// JavaScript implementation of
// the above approach
// Function that prints the
// number of different strings
// that can be formed
function differentStrings(s)
{
// Computing the length of
// the given string
var n = s.length;
var dp = Array(n + 1);
// Base case
dp[0] = dp[1] = 1;
// Traverse the given string
for (var i = 1; i < n; i++) {
// If two consecutive 1's
// or 2's are present
if (s[i] == s[i - 1]
&& (s[i] == '1'
|| s[i] == '2'))
dp[i + 1]
= dp[i] + dp[i - 1];
// Otherwise take
// the previous value
else
dp[i + 1] = dp[i];
}
document.write( dp[n] + "<br>");
}
// Driver Code
var S = "0111022110";
differentStrings(S);
</script>
12
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces, por lo que nos costará O (N) tiempo
Espacio auxiliar: O (N), ya que estamos usando espacio adicional para la array DP.
Publicación traducida automáticamente
Artículo escrito por nitinkr8991 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA