Dynamic Programming | Set 19 (Word Wrap Problem) | GeeksforGeeks
Given a sequence of words, and a limit on the number of characters that can be put in one line (line width). Put line breaks in the given sequence such that the lines are printed neatly. Assume that the length of each word is smaller than the line width.
Please note that the total cost function is not sum of extra spaces, but sum of cubes (or square is also used) of extra spaces. The idea behind this cost function is to balance the spaces among lines.
Method 2 (Dynamic Programming)
Time Complexity: O(n^2)
Auxiliary Space: O(n^2) The auxiliary space used in the above program cane be optimized to O(n)
To print the output, we keep track of what words go on what lines, we can keep a parallel p array that points to where each c value came from. The last line starts at word p[n] and goes through word n. The previous line starts at word p[p[n]] and goes through word p[n] – 1, etc. The function printSolution() uses p[] to print the solution.Greedy Implementation: http://rosettacode.org/wiki/Word_wrap#Java
Method 1 (Greedy Solution)
The greedy solution is to place as many words as possible in the first line. Then do the same thing for the second line and so on until all words are placed. This solution gives optimal solution for many cases, but doesn’t give optimal solution in all cases.
Given a sequence of words, and a limit on the number of characters that can be put in one line (line width). Put line breaks in the given sequence such that the lines are printed neatly. Assume that the length of each word is smaller than the line width.
Please note that the total cost function is not sum of extra spaces, but sum of cubes (or square is also used) of extra spaces. The idea behind this cost function is to balance the spaces among lines.
Method 2 (Dynamic Programming)
Time Complexity: O(n^2)
Auxiliary Space: O(n^2) The auxiliary space used in the above program cane be optimized to O(n)
First we compute costs of all possible lines in a 2D table lc[][].
The value lc[i][j] indicates the cost to put words from i to j in a single line where i and j are indexes of words in the input sequences. If a sequence of words from i to j cannot fit in a single line, then lc[i][j] is considered infinite (to avoid it from being a part of the solution). Once we have the lc[][] table constructed, we can calculate total cost using following recursive formula.
In the following formula, C[j] is the optimized total cost for arranging words from 1 to j.
The value lc[i][j] indicates the cost to put words from i to j in a single line where i and j are indexes of words in the input sequences. If a sequence of words from i to j cannot fit in a single line, then lc[i][j] is considered infinite (to avoid it from being a part of the solution). Once we have the lc[][] table constructed, we can calculate total cost using following recursive formula.
In the following formula, C[j] is the optimized total cost for arranging words from 1 to j.
void solveWordWrap (int l[], int n, int M){ // For simplicity, 1 extra space is used in all below arrays // extras[i][j] will have number of extra spaces if words from i // to j are put in a single line int extras[n+1][n+1]; // lc[i][j] will have cost of a line which has words from // i to j int lc[n+1][n+1]; // c[i] will have total cost of optimal arrangement of words // from 1 to i int c[n+1]; // p[] is used to print the solution. int p[n+1]; int i, j; // calculate extra spaces in a single line. The value extra[i][j] // indicates extra spaces if words from word number i to j are // placed in a single line for (i = 1; i <= n; i++) { extras[i][i] = M - l[i-1]; for (j = i+1; j <= n; j++) extras[i][j] = extras[i][j-1] - l[j-1] - 1; } // Calculate line cost corresponding to the above calculated extra // spaces. The value lc[i][j] indicates cost of putting words from // word number i to j in a single line for (i = 1; i <= n; i++) { for (j = i; j <= n; j++) { if (extras[i][j] < 0) lc[i][j] = INF; else if (j == n && extras[i][j] >= 0) lc[i][j] = 0; else lc[i][j] = extras[i][j]*extras[i][j]; } } // Calculate minimum cost and find minimum cost arrangement. // The value c[j] indicates optimized cost to arrange words // from word number 1 to j. c[0] = 0; for (j = 1; j <= n; j++) { c[j] = INF; for (i = 1; i <= j; i++) { if (c[i-1] != INF && lc[i][j] != INF && (c[i-1] + lc[i][j] < c[j])) { c[j] = c[i-1] + lc[i][j]; p[j] = i; } } } printSolution(p, n);}int printSolution (int p[], int n){ int k; if (p[n] == 1) k = 1; else k = printSolution (p, p[n]-1) + 1; printf ("Line number %d: From word no. %d to %d \n", k, p[n], n); return k;}
EPI Java Solution: The pretty printing problem
public static int findPrettyPrinting(List<String> W, int L) {
// Calculates M(i).
long[] M = new long[W.size()];
Arrays.fill(M, Long.MAX_VALUE);
for (int i = 0; i < W.size(); ++i) {
int bLen = L - W.get(i).length();
M[i] = Math.min((i - 1 < 0 ? 0 : M[i - 1]) + (1 << bLen), M[i]);
for (int j = i - 1; j >= 0; --j) {
bLen -= (W.get(j).length() + 1);
if (bLen < 0) {
break;
}
M[i] = Math.min((j - 1 < 0 ? 0 : M[j - 1]) + (1 << bLen), M[i]);
}
}
// Finds the minimum cost without considering the last line.
long minMess = (W.size() >= 2 ? M[W.size() - 2] : 0);
int bLen = L - W.get(W.size() - 1).length();
for (int i = W.size() - 2; i >= 0; --i) {
bLen -= (W.get(i).length() + 1);
if (bLen < 0) {
return (int) minMess;
}
minMess = Math.min(minMess, (i - 1 < 0 ? 0 : M[i - 1]));
}
return (int) minMess;
}The greedy solution is to place as many words as possible in the first line. Then do the same thing for the second line and so on until all words are placed. This solution gives optimal solution for many cases, but doesn’t give optimal solution in all cases.
Despite being sub-optimal in some cases, the greedy approach is used by many word processors like MS Word and OpenOffice.org Writer.Read full article from Dynamic Programming | Set 19 (Word Wrap Problem) | GeeksforGeeks
