Dada una secuencia de palabras y un límite en el número de caracteres que se pueden poner en una línea (ancho de línea). Coloque saltos de línea en la secuencia dada de modo que las líneas se impriman con claridad. Suponga que la longitud de cada palabra es más pequeña que el ancho de la línea. Cuando se insertan saltos de línea, existe la posibilidad de que haya espacios adicionales en cada línea. Los espacios adicionales incluyen espacios colocados al final de cada línea excepto la última.
El problema es minimizar el siguiente costo total.
Costo total = Suma del costo de todas las líneas, donde el costo de la línea es = (Número de espacios adicionales en la línea)^2.
Por ejemplo, considere la siguiente string y ancho de línea M = 15
«Geeks for Geeks presenta un problema de ajuste de palabras»
A continuación se muestra la disposición optimizada de las palabras en 3 líneas
Geeks for Geeks
presenta el
problema del ajuste de palabras
El total de espacios adicionales en la línea 1 y la línea 2 son 0 y 2. El espacio para la línea 3 no se considera porque no es espacio adicional como se describe anteriormente. Entonces, el valor óptimo del costo total es 0 + 2*2 = 4.
Ejemplos:
Input format: Input will consists of array of integers where each array element represents length of each word of string. For example, for string S = "Geeks for Geeks", input array will be arr[] = {5, 3, 5}.
Output format: Output consists of a series of integers where two consecutive integers represent
starting word and ending word of each line.
Input : arr[] = {3, 2, 2, 5}
Output : 1 1 2 3 4 4
Line number 1: From word no. 1 to 1
Line number 2: From word no. 2 to 3
Line number 3: From word no. 4 to 4
Input : arr[] = {3, 2, 2}
Output : 1 1 2 2 3 3
Line number 1: From word no. 1 to 1
Line number 2: From word no. 2 to 2
Line number 3: From word no. 3 to 3
Enfoque: Hemos discutido una solución basada en Programación Dinámicadel problema de ajuste de palabras. La solución discutida usó el espacio auxiliar O (n ^ 2). El espacio auxiliar utilizado se puede reducir a O(n). La idea es usar dos arrays 1-D dp[] y ans[], donde dp[i] representa el costo mínimo de la línea en la que arr[i] es la primera palabra y ans[i] representa el índice de la última palabra presente en línea en la que la palabra arr[i] es la primera palabra. Deje que k represente el límite en el número de caracteres en cada línea. Supongamos que para cualquier línea l, la primera palabra de esa línea está en el índice i en arr[]. El costo mínimo de esa línea se almacena en dp[i]. La última palabra de esa línea está en el índice j en arr[], donde j puede variar de i a n. Repita todos los valores de j y realice un seguimiento de la cantidad de caracteres agregados hasta ahora en la línea l. Si el número de caracteres es menor que k, encuentre el costo de la línea actual con este número de caracteres. Compare este costo con el costo mínimo encontrado hasta ahora para esta línea en dp[i] y actualice dp[i] y ans[i] en consecuencia. Repita el procedimiento anterior para cada valor de i, 1 <= i <= n. Las palabras iniciales y finales de cada línea estarán en el índice i y en el índice ans[i], donde el siguiente valor de i para la línea l+1 es ans[i] + 1.
Implementación:
C++
// C++ program for space optimized
// solution of Word Wrap problem.
#include <bits/stdc++.h>
using namespace std;
// Function to find space optimized
// solution of Word Wrap problem.
void solveWordWrap(int arr[], int n, int k)
{
int i, j;
// Variable to store number of
// characters in given line.
int currlen;
// Variable to store possible
// minimum cost of line.
int cost;
// DP table in which dp[i] represents
// cost of line starting with word
// arr[i].
int dp[n];
// Array in which ans[i] store index
// of last word in line starting with
// word arr[i].
int ans[n];
// If only one word is present then
// only one line is required. Cost
// of last line is zero. Hence cost
// of this line is zero. Ending point
// is also n-1 as single word is
// present.
dp[n - 1] = 0;
ans[n - 1] = n - 1;
// Make each word first word of line
// by iterating over each index in arr.
for (i = n - 2; i >= 0; i--) {
currlen = -1;
dp[i] = INT_MAX;
// Keep on adding words in current
// line by iterating from starting
// word upto last word in arr.
for (j = i; j < n; j++) {
// Update number of characters
// in current line. arr[j] is
// number of characters in
// current word and 1
// represents space character
// between two words.
currlen += (arr[j] + 1);
// If limit of characters
// is violated then no more
// words can be added to
// current line.
if (currlen > k)
break;
// If current word that is
// added to line is last
// word of arr then current
// line is last line. Cost of
// last line is 0. Else cost
// is square of extra spaces
// plus cost of putting line
// breaks in rest of words
// from j+1 to n-1.
if (j == n - 1)
cost = 0;
else
cost = (k - currlen) * (k - currlen) + dp[j + 1];
// Check if this arrangement gives
// minimum cost for line starting
// with word arr[i].
if (cost < dp[i]) {
dp[i] = cost;
ans[i] = j;
}
}
}
// Print starting index and ending index
// of words present in each line.
i = 0;
while (i < n) {
cout << i + 1 << " " << ans[i] + 1 << " ";
i = ans[i] + 1;
}
}
// Driver function
int main()
{
int arr[] = { 3, 2, 2, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int M = 6;
solveWordWrap(arr, n, M);
return 0;
}
Java
// Java program for space
// optimized solution of
// Word Wrap problem.
import java.io.*;
class GFG
{
// Function to find space
// optimized solution of
// Word Wrap problem.
static void solveWordWrap(int arr[],
int n, int k)
{
int i, j;
// Variable to store
// number of characters
// in given line.
int currlen;
// Variable to store
// possible minimum
// cost of line.
int cost;
// DP table in which
// dp[i] represents
// cost of line starting
// with word arr[i].
int dp[] = new int[n];
// Array in which ans[i]
// store index of last
// word in line starting
// with word arr[i].
int ans[] = new int[n];
// If only one word is present
// then only one line is required.
// Cost of last line is zero.
// Hence cost of this line is zero.
// Ending point is also n-1 as
// single word is present.
dp[n - 1] = 0;
ans[n - 1] = n - 1;
// Make each word first
// word of line by iterating
// over each index in arr.
for (i = n - 2; i >= 0; i--)
{
currlen = -1;
dp[i] = Integer.MAX_VALUE;
// Keep on adding words in
// current line by iterating
// from starting word upto
// last word in arr.
for (j = i; j < n; j++)
{
// Update number of characters
// in current line. arr[j] is
// number of characters in
// current word and 1
// represents space character
// between two words.
currlen += (arr[j] + 1);
// If limit of characters
// is violated then no more
// words can be added to
// current line.
if (currlen > k)
break;
// If current word that is
// added to line is last
// word of arr then current
// line is last line. Cost of
// last line is 0. Else cost
// is square of extra spaces
// plus cost of putting line
// breaks in rest of words
// from j+1 to n-1.
if (j == n - 1)
cost = 0;
else
cost = (k - currlen) *
(k - currlen) +
dp[j + 1];
// Check if this arrangement
// gives minimum cost for
// line starting with word
// arr[i].
if (cost < dp[i])
{
dp[i] = cost;
ans[i] = j;
}
}
}
// Print starting index
// and ending index of
// words present in each line.
i = 0;
while (i < n)
{
System.out.print((i + 1) + " " +
(ans[i] + 1) + " ");
i = ans[i] + 1;
}
}
// Driver Code
public static void main (String[] args)
{
int arr[] = {3, 2, 2, 5};
int n = arr.length;
int M = 6;
solveWordWrap(arr, n, M);
}
}
// This code is contributed
// by anuj_67.
Python 3
# Python 3 program for space optimized # solution of Word Wrap problem. import sys # Function to find space optimized # solution of Word Wrap problem. def solveWordWrap(arr, n, k): dp = [0] * n # Array in which ans[i] store index # of last word in line starting with # word arr[i]. ans = [0] * n # If only one word is present then # only one line is required. Cost # of last line is zero. Hence cost # of this line is zero. Ending point # is also n-1 as single word is # present. dp[n - 1] = 0 ans[n - 1] = n - 1 # Make each word first word of line # by iterating over each index in arr. for i in range(n - 2, -1, -1): currlen = -1 dp[i] = sys.maxsize # Keep on adding words in current # line by iterating from starting # word upto last word in arr. for j in range(i, n): # Update number of characters # in current line. arr[j] is # number of characters in # current word and 1 # represents space character # between two words. currlen += (arr[j] + 1) # If limit of characters # is violated then no more # words can be added to # current line. if (currlen > k): break # If current word that is # added to line is last # word of arr then current # line is last line. Cost of # last line is 0. Else cost # is square of extra spaces # plus cost of putting line # breaks in rest of words # from j+1 to n-1. if (j == n - 1): cost = 0 else: cost = ((k - currlen) * (k - currlen) + dp[j + 1]) # Check if this arrangement gives # minimum cost for line starting # with word arr[i]. if (cost < dp[i]): dp[i] = cost ans[i] = j # Print starting index and ending index # of words present in each line. i = 0 while (i < n): print(i + 1 , ans[i] + 1, end = " ") i = ans[i] + 1 # Driver Code if __name__ == "__main__": arr = [3, 2, 2, 5 ] n = len(arr) M = 6 solveWordWrap(arr, n, M) # This code is contributed by ita_c
C#
// C# program for space
// optimized solution of
// Word Wrap problem.
using System;
class GFG
{
// Function to find space optimized
// solution of Word Wrap problem.
public static void solveWordWrap(int[] arr,
int n, int k)
{
int i, j;
// Variable to store number of
// characters in given line.
int currlen;
// Variable to store possible
// minimum cost of line.
int cost;
// DP table in which dp[i]
// represents cost of line
// starting with word arr[i].
int[] dp = new int[n];
// Array in which ans[i] store
// index of last word in line
// starting with word arr[i].
int[] ans = new int[n];
// If only one word is present
// then only one line is required.
// Cost of last line is zero.
// Hence cost of this line is zero.
// Ending point is also n-1 as
// single word is present.
dp[n - 1] = 0;
ans[n - 1] = n - 1;
// Make each word first
// word of line by iterating
// over each index in arr.
for (i = n - 2; i >= 0; i--)
{
currlen = -1;
dp[i] = int.MaxValue;
// Keep on adding words in
// current line by iterating
// from starting word upto
// last word in arr.
for (j = i; j < n; j++)
{
// Update number of characters
// in current line. arr[j] is
// number of characters in
// current word and 1
// represents space character
// between two words.
currlen += (arr[j] + 1);
// If limit of characters
// is violated then no more
// words can be added to
// current line.
if (currlen > k)
{
break;
}
// If current word that is
// added to line is last
// word of arr then current
// line is last line. Cost of
// last line is 0. Else cost
// is square of extra spaces
// plus cost of putting line
// breaks in rest of words
// from j+1 to n-1.
if (j == n - 1)
{
cost = 0;
}
else
{
cost = (k - currlen) *
(k - currlen) + dp[j + 1];
}
// Check if this arrangement
// gives minimum cost for
// line starting with word
// arr[i].
if (cost < dp[i])
{
dp[i] = cost;
ans[i] = j;
}
}
}
// Print starting index
// and ending index of
// words present in each line.
i = 0;
while (i < n)
{
Console.Write((i + 1) + " " +
(ans[i] + 1) + " ");
i = ans[i] + 1;
}
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = new int[] {3, 2, 2, 5};
int n = arr.Length;
int M = 6;
solveWordWrap(arr, n, M);
}
}
// This code is contributed
// by Shrikant13
PHP
<?php
// PHP program for space optimized
// solution of Word Wrap problem.
// Function to find space optimized
// solution of Word Wrap problem.
function solveWordWrap($arr, $n, $k)
{
// Variable to store number of
// characters in given line.
$currlen;
// Variable to store possible
// minimum cost of line.
$cost;
// DP table in which dp[i] represents
// cost of line starting with word
// arr[i].
$dp = array();
// Array in which ans[i] store index
// of last word in line starting with
// word arr[i].
$ans = array();
// If only one word is present then
// only one line is required. Cost
// of last line is zero. Hence cost
// of this line is zero. Ending point
// is also n-1 as single word is
// present.
$dp[$n - 1] = 0;
$ans[$n - 1] = $n - 1;
// Make each word first word of line
// by iterating over each index in arr.
for ($i = $n - 2; $i >= 0; $i--)
{
$currlen = -1;
$dp[$i] = PHP_INT_MAX;
// Keep on adding words in current
// line by iterating from starting
// word upto last word in arr.
for ($j = $i; $j < $n; $j++)
{
// Update number of characters
// in current line. arr[j] is
// number of characters in
// current word and 1
// represents space character
// between two words.
$currlen += ($arr[$j] + 1);
// If limit of characters
// is violated then no more
// words can be added to
// current line.
if ($currlen > $k)
break;
// If current word that is
// added to line is last
// word of arr then current
// line is last line. Cost of
// last line is 0. Else cost
// is square of extra spaces
// plus cost of putting line
// breaks in rest of words
// from j+1 to n-1.
if ($j == $n - 1)
$cost = 0;
else
$cost = ($k - $currlen) *
($k - $currlen) + $dp[$j + 1];
// Check if this arrangement gives
// minimum cost for line starting
// with word arr[i].
if ($cost < $dp[$i])
{
$dp[$i] = $cost;
$ans[$i] = $j;
}
}
}
// Print starting index and ending index
// of words present in each line.
$i = 0;
while ($i < $n)
{
echo ($i + 1) . " " .
($ans[$i] + 1) . " ";
$i = $ans[$i] + 1;
}
}
// Driver function
$arr = array(3, 2, 2, 5);
$n = sizeof($arr);
$M = 6;
solveWordWrap($arr, $n, $M);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript program for space optimized
// solution of Word Wrap problem.
// Function to find space optimized
// solution of Word Wrap problem.
function solveWordWrap(arr, n, k)
{
var i, j;
// Variable to store number of
// characters in given line.
var currlen;
// Variable to store possible
// minimum cost of line.
var cost;
// DP table in which dp[i] represents
// cost of line starting with word
// arr[i].
var dp = Array(n);
// Array in which ans[i] store index
// of last word in line starting with
// word arr[i].
var ans = Array(n);
// If only one word is present then
// only one line is required. Cost
// of last line is zero. Hence cost
// of this line is zero. Ending point
// is also n-1 as single word is
// present.
dp[n - 1] = 0;
ans[n - 1] = n - 1;
// Make each word first word of line
// by iterating over each index in arr.
for (i = n - 2; i >= 0; i--)
{
currlen = -1;
dp[i] = 1000000000;
// Keep on adding words in current
// line by iterating from starting
// word upto last word in arr.
for (j = i; j < n; j++)
{
// Update number of characters
// in current line. arr[j] is
// number of characters in
// current word and 1
// represents space character
// between two words.
currlen += (arr[j] + 1);
// If limit of characters
// is violated then no more
// words can be added to
// current line.
if (currlen > k)
break;
// If current word that is
// added to line is last
// word of arr then current
// line is last line. Cost of
// last line is 0. Else cost
// is square of extra spaces
// plus cost of putting line
// breaks in rest of words
// from j+1 to n-1.
if (j == n - 1)
cost = 0;
else
cost = (k - currlen) * (k - currlen) + dp[j + 1];
// Check if this arrangement gives
// minimum cost for line starting
// with word arr[i].
if (cost < dp[i]) {
dp[i] = cost;
ans[i] = j;
}
}
}
// Print starting index and ending index
// of words present in each line.
i = 0;
while (i < n)
{
document.write( i + 1 + " " + (ans[i] + 1) + " ");
i = ans[i] + 1;
}
}
// Driver function
var arr = [ 3, 2, 2, 5 ];
var n = arr.length;
var M = 6;
solveWordWrap(arr, n, M);
// This code is contributed by itsok.
</script>
Producción:
1 1 2 3 4 4
Complejidad de tiempo: O(n^2)
Espacio auxiliar: O(n)