Dada una string numérica S , la tarea es encontrar el número de formas de dividir una string en substrings que consisten en dígitos en orden creciente.
Ejemplos:
Entrada: S = “1345”
Salida: 5
Explicación: Las posibles particiones son las siguientes:
- [1345]
- [13, 45], [1, 345]
- [1, 3, 45]
- [1, 3, 4, 5]
Entrada: S = “12”
Salida: 2
Planteamiento: Este problema se puede resolver observando que entre cada dígito será parte del número anterior o será un número nuevo, por lo que para resolver el problema se puede utilizar la recursividad . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable entera, digamos contar como 0 , para almacenar el número de formas de dividir una string en subconjuntos crecientes.
- Declare una función print() con índice (almacenando la posición actual), string S (string dada en la pregunta) y string ans (como parámetros.
- Ahora bien, se deben considerar los siguientes dos casos:
- Si se inserta S[index] en el número anterior, agregue S[index] al final de ans y recupere la función print() con los parámetros index + 1 , S y ans .
- Si S[índice] no es parte del número anterior, agregue ” “ (espacio) al final de ans y luego inserte S[índice] y recupere la función imprimir() con los parámetros índice + 1 , S , ans .
- Si index = S.length() , compruebe si los dígitos de las secuencias formadas están en orden creciente o no. Si las secuencias formadas son crecientes, aumente la cuenta en 1 .
- Imprima el conteo como la respuesta después de realizar los pasos anteriores.
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;
// Stores the number of ways
// to partition a string
int count1 = 0;
vector<string> split(string str)
{
vector<string> ans;
string word = "";
for(auto x : str)
{
if (x == ' ')
{
ans.push_back(word);
word = "";
}
else
{
word = word + x;
}
}
ans.push_back(word);
return ans;
}
// Function to check if a sequence
// is strictly increasing or not
bool check(string m)
{
// If there is only one number
if (m.length() == 1)
{
return true;
}
// Split the string m when there is space
vector<string> temp = split(m);
int number[temp.size()];
// Insert all the splits into the array
for(int i = 0; i < temp.size(); ++i)
{
number[i] = stoi(temp[i]);
}
int first = number[0];
for(int i = 1; i < temp.size(); ++i)
{
if (number[i] > first)
{
first = number[i];
}
else
{
// If number is not increasing
return false;
}
}
// If the sequence is increasing
return true;
}
// Recursive function to partition
// a string in every possible substrings
void print1(string m, int index, string ans)
{
// If index = m.length, check if ans
// forms an increasing sequence or not
if (index == m.length())
{
if (check(ans))
{
// Increment count by 1,
// if sequence is increasing
count1++;
}
return;
}
// If S[index] is appended to previous number
print1(m, index + 1, ans + m[index]);
if (index != 0)
// If S[index] is starting a new number
print1(m, index + 1,
ans + " " + m[index]);
}
// Driver Code
int main()
{
// Given Input
string k = "1345";
// Function Call
print1(k, 0, "");
// Print the answer.
cout << count1;
}
// This code is contributed by ipg2016107
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Stores the number of ways
// to partition a string
static int count = 0;
// Function to check if a sequence
// is strictly increasing or not
static boolean check(String m)
{
// If there is only one number
if (m.length() == 1) {
return true;
}
// Split the string m when there is space
String temp[] = m.split(" ");
int number[] = new int[temp.length];
// Insert all the splits into the array
for (int i = 0; i < temp.length; ++i) {
number[i] = Integer.parseInt(temp[i]);
}
int first = number[0];
for (int i = 1; i < number.length; ++i) {
if (number[i] > first) {
first = number[i];
}
else {
// If number is not increasing
return false;
}
}
// If the sequence is increasing
return true;
}
// Recursive function to partition
// a string in every possible substrings
static void print(String m,
int index, String ans)
{
// If index = m.length, check if ans
// forms an increasing sequence or not
if (index == m.length()) {
if (check(ans)) {
// Increment count by 1,
// if sequence is increasing
++count;
}
return;
}
// If S[index] is appended to previous number
print(m, index + 1, ans + m.charAt(index));
if (index != 0)
// If S[index] is starting a new number
print(m, index + 1,
ans + " " + m.charAt(index));
}
// DriverCode
public static void main(String[] args)
{
// Given Input
String k = Integer.toString(1345);
// Function Call
print(k, 0, "");
// Print the answer.
System.out.println(count);
}
}
Python3
# Python3 program for the above approach
count = 0
# Function to check if a sequence
# is strictly increasing or not
def check(m):
# If there is only one number
if (len(m) == 1):
return True
# Split the string m when there is space
temp = m.split(" ")
number = [0]*(len(temp))
# Insert all the splits into the array
for i in range(len(temp)):
number[i] = int(temp[i])
first = number[0]
for i in range(1, len(number)):
if (number[i] > first):
first = number[i]
else:
# If number is not increasing
return False
# If the sequence is increasing
return True
# Recursive function to partition
# a string in every possible substrings
def Print(m, index, ans):
global count
# If index = m.length, check if ans
# forms an increasing sequence or not
if (index == len(m)):
if (check(ans)):
# Increment count by 1,
# if sequence is increasing
count+=1
return
# If S[index] is appended to previous number
Print(m, index + 1, ans + m[index])
if (index != 0):
# If S[index] is starting a new number
Print(m, index + 1, ans + " " + m[index])
# Given Input
k = "1345"
# Function Call
Print(k, 0, "")
# Print the answer.
print(count)
# This code is contributed by suresh07.
C#
using System;
public class GFG {
static int count = 0;
// Function to check if a sequence
// is strictly increasing or not
static bool check(String m)
{
// If there is only one number
if (m.Length == 1) {
return true;
}
// Split the string m when there is space
String[] temp = m.Split(" ");
int[] number = new int[temp.Length];
// Insert all the splits into the array
for (int i = 0; i < temp.Length; ++i) {
number[i] = int.Parse(temp[i]);
}
int first = number[0];
for (int i = 1; i < number.Length; ++i) {
if (number[i] > first) {
first = number[i];
}
else {
// If number is not increasing
return false;
}
}
// If the sequence is increasing
return true;
}
// Recursive function to partition
// a string in every possible substrings
static void print(String m, int index, String ans)
{
// If index = m.length, check if ans
// forms an increasing sequence or not
if (index == m.Length) {
if (check(ans)) {
// Increment count by 1,
// if sequence is increasing
++count;
}
return;
}
// If S[index] is appended to previous number
print(m, index + 1, ans + m[index]);
if (index != 0)
// If S[index] is starting a new number
print(m, index + 1, ans + " " + m[index]);
}
static public void Main()
{
String k = "1345";
// Function Call
print(k, 0, "");
// Print the answer.
Console.WriteLine(count);
}
}
// This code is contributed by maddler.
Javascript
<script>
// JavaScript program for the above approach
// Stores the number of ways
// to partition a string
let count = 0;
// Function to check if a sequence
// is strictly increasing or not
function check(m)
{
// If there is only one number
if (m.length == 1)
{
return true;
}
// Split the string m when there is space
let temp = m.split(" ");
let number = new Array(temp.length);
// Insert all the splits into the array
for(let i = 0; i < temp.length; ++i)
{
number[i] = parseInt(temp[i]);
}
let first = number[0];
for(let i = 1; i < number.length; ++i)
{
if (number[i] > first)
{
first = number[i];
}
else
{
// If number is not increasing
return false;
}
}
// If the sequence is increasing
return true;
}
// Recursive function to partition
// a string in every possible substrings
function print(m, index, ans)
{
// If index = m.length, check if ans
// forms an increasing sequence or not
if (index == m.length)
{
if (check(ans))
{
// Increment count by 1,
// if sequence is increasing
++count;
}
return;
}
// If S[index] is appended to previous number
print(m, index + 1, ans + m[index]);
if (index != 0)
// If S[index] is starting a new number
print(m, index + 1,
ans + " " + m[index]);
}
// Driver Code
// Given Input
let k = "1345";
// Function Call
print(k, 0, "");
// Print the answer.
document.write(count);
// This code is contributed by code_hunt
</script>
Producción:
5
Complejidad de tiempo: O(N*2 N ) donde N es la longitud de la string S
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA