Dada una string S , la tarea es encontrar el número de formas de dividir/particionar la string dada en substrings S1, S2, S3, …, Sk tales que S1 < S2 < S3 < … < Sk (lexicográficamente).
Ejemplos:
Entrada: S = “aabc”
Salida: 6
Las siguientes son las particiones permitidas:
{“aabc”}, {“aa”, “bc”}, {“aab”, “c”}, {“a”, “abc” },
{“a, “ab”, “c”} y {“aa”, “b”, “c”}.Entrada: S = “za”
Salida: 1 La
única partición posible es {“za”}.
Enfoque: Este problema se puede resolver mediante programación dinámica .
- Defina DP[i][j] como el número de formas de dividir la substring S[0…j] de modo que S[i, j] sea la última partición.
- Ahora, las relaciones de recurrencia serán DP[i][j] = Suma de (DP[k][i – 1]) para todo k ≥ 0 e i ≤ N – 1 donde N es la longitud de la string.
- La respuesta final será la suma de (DP[i][N – 1]) para todos los i entre 0 y N – 1, ya que estas substrings se convertirán en la última partición de alguna forma posible de partición.
- Entonces, aquí para todas las substrings S[i][j] , encuentre la substring S[k][i – 1] tal que S[k][i – 1] sea lexicográficamente menor que S[i] [j] y agregue DP[k][i – 1] a DP[i][j] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the number of
// ways of partitioning
int ways(string s, int n)
{
int dp[n][n];
// Initialize DP table
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
dp[i][j] = 0;
}
// Base Case
for (int i = 0; i < n; i++)
dp[0][i] = 1;
for (int i = 1; i < n; i++) {
// To store sub-string S[i][j]
string temp;
for (int j = i; j < n; j++) {
temp += s[j];
// To store sub-string S[k][i-1]
string test;
for (int k = i - 1; k >= 0; k--) {
test += s[k];
if (test < temp) {
dp[i][j] += dp[k][i - 1];
}
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
// Add all the ways where S[i][n-1]
// will be the last partition
ans += dp[i][n - 1];
}
return ans;
}
// Driver code
int main()
{
string s = "aabc";
int n = s.length();
cout << ways(s, n);
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
// Function to return the number of
// ways of partitioning
static int ways(String s, int n)
{
int dp[][] = new int[n][n];
// Initialize DP table
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
dp[i][j] = 0;
}
// Base Case
for (int i = 0; i < n; i++)
dp[0][i] = 1;
for (int i = 1; i < n; i++)
{
// To store sub-string S[i][j]
String temp = "";
for (int j = i; j < n; j++)
{
temp += s.charAt(j);
// To store sub-string S[k][i-1]
String test = "";
for (int k = i - 1; k >= 0; k--)
{
test += s.charAt(k);
if (test.compareTo(temp) < 0)
{
dp[i][j] += dp[k][i - 1];
}
}
}
}
int ans = 0;
for (int i = 0; i < n; i++)
{
// Add all the ways where S[i][n-1]
// will be the last partition
ans += dp[i][n - 1];
}
return ans;
}
// Driver code
public static void main (String[] args)
{
String s = "aabc";
int n = s.length();
System.out.println(ways(s, n));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to return the number of # ways of partitioning def ways(s, n): dp = [[0 for i in range(n)] for i in range(n)] # Base Case for i in range(n): dp[0][i] = 1 for i in range(1, n): # To store sub-S[i][j] temp = "" for j in range(i, n): temp += s[j] # To store sub-S[k][i-1] test = "" for k in range(i - 1, -1, -1): test += s[k] if (test < temp): dp[i][j] += dp[k][i - 1] ans = 0 for i in range(n): # Add all the ways where S[i][n-1] # will be the last partition ans += dp[i][n - 1] return ans # Driver code s = "aabc" n = len(s) print(ways(s, n)) # This code is contributed by Mohit Kumarv
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to return the number of
// ways of partitioning
static int ways(String s, int n)
{
int [,]dp = new int[n, n];
// Initialize DP table
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
dp[i, j] = 0;
}
// Base Case
for (int i = 0; i < n; i++)
dp[0, i] = 1;
for (int i = 1; i < n; i++)
{
// To store sub-string S[i,j]
String temp = "";
for (int j = i; j < n; j++)
{
temp += s[j];
// To store sub-string S[k,i-1]
String test = "";
for (int k = i - 1; k >= 0; k--)
{
test += s[k];
if (test.CompareTo(temp) < 0)
{
dp[i, j] += dp[k, i - 1];
}
}
}
}
int ans = 0;
for (int i = 0; i < n; i++)
{
// Add all the ways where S[i,n-1]
// will be the last partition
ans += dp[i, n - 1];
}
return ans;
}
// Driver code
public static void Main (String[] args)
{
String s = "aabc";
int n = s.Length;
Console.WriteLine(ways(s, n));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
// Function to return the number of
// ways of partitioning
function ways(s, n)
{
var dp = Array.from(Array(n), ()=> Array(n).fill(0));
// Base Case
for (var i = 0; i < n; i++)
dp[0][i] = 1;
for (var i = 1; i < n; i++) {
// To store sub-string S[i][j]
var temp;
for (var j = i; j < n; j++) {
temp += s[j];
// To store sub-string S[k][i-1]
var test;
for (var k = i - 1; k >= 0; k--) {
test += s[k];
if (test < temp) {
dp[i][j] += dp[k][i - 1];
}
}
}
}
var ans = 0;
for (var i = 0; i < n; i++) {
// Add all the ways where S[i][n-1]
// will be the last partition
ans += dp[i][n - 1];
}
return ans;
}
// Driver code
var s = "aabc";
var n = s.length;
document.write( ways(s, n));
// This code is contributed by itsok.
</script>
Producción:
6
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(n 2 )