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