Word Wrap Problem

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

In this article, we have solved the Word Wrap Problem in depth. This involves Dynamic Programming Concepts.

What is Word Wrap Problem?

You are given ‘n’ words of various lengths, and a limit on the number of characters that can be put in one line (width of line: 'w'). Assume each word has length less than the width of line(w). You have to arrange these given words in such a way that:

Each word is separated by a space character.
You need to put as many as words in every line.
You can not spilt the words and put them in next line.
Extra spaces includes spaces put at the end of every line except the last line.
Example for Extra spaces: Let take an array A={aaa, bbb, cc, dddd} and length of line=6.

a a a _ _ _
b b b ~ c c
d d d d _ _

So, Extra spaces are shown with the help of underscore(_) and spaces in mid of word are shown with the help of tild(~).

Objective:

The problem is to minimize the total cost.
Total cost= Sum of costs of all lines

There are two methods to find cost of a line:

Cost of a line= (number of spaces in each line)^3
Cost of a line= (number of spaces in each line)^2
In our algorithm, we will be using method-2 to find cost of a line.

Word wrap problem VS Word break problem

Word wrap problem : It does not split the word into parts istead it wrap the word into next line.
Example:
Let the length of line be 6.
Array = {"He", "like", "to", "sing"}

He 
like 
to
sing

Here each is having length=6 and after putting the a word another word can not be put in same line, so we have to put it in next line.
Word break problem:
As the name represents "word-break" break the word.
It breaks the word at any character due to which the result is hard to understand.
Example:
Let the length of line be 6.
Array = {"He", "like", "to", "sing"}

He lik
e to s
ing

Here If a line does not enough space to write full word, so with help of word-break algorithm, word will be break into parts as shown in example.

Learn with a Problem

We can do this problem using Greedy method and Dyanamic Programming, Here we will be using Dynamic Programming method.

Lets take an array A containing words {"she", "is", "my", "soul"} and also take length of line or width of line, w=6.

First we will put 1st word in a line.

she

Here, word "she" is taking 3 length space due to which now 1st line is only having 3 more spaces left which count in extra spaces, so cost of line = (number of spaces in each line)^2
cost of 1st line = ( 3 )^2 = 9
2. Now,put 2nd word in second line( To know why are we putting 2nd word in second line, read the NOTE after reaing these points).

she
is

Here, "is" word is taking 2 length space, now we have 4 extra spaces left.
Therefore, cost of 2nd line = ( 4 )^2 = 16
3. Now, put 3rd word in the Second line, according to the above mentioned conditions.

she
is my

Here, after putting 3rd word in 2nd line, we are having only one(1) extra space left.
New Cost of 2nd line = ( 1 )^2 = 1.
4. Put the 4th word in the third line.

she
is my
soul

Here only 2 extra spaces remains.
Cost of 3rd line = ( 2 )^2 = 4.
Therefore, Total cost = sum of all lines = 9 + 1 + 4 = 14
Total cost = 14.

Note:

Why did we put word "is" in second line instead of putting it in first line, when was still some space to write?

Because if we write word "is" in 1st line then there will be no extra space left so,
Cost of 1st line = (0)^2 = 0

Later on, when we put the 3rd word in 2nd line there will be 4 extra space left and we can not put word "soul" of length=4 in those remaining 4 extra space because "there should be a gap in between two words" due to which,

Cost of 2nd line = (4)^2 = 16
And then the Cost of 3rd line = (2)^2 = 4
Total cost = 0 + 16 + 4 = 20
Total cost will increase.

Algorithm for word wrap problem

Let take an array containing words 'A' and width of line 'w', given by user.
Word size as "ws", it is an array(ws[]) containing word size of 'A' on respective indices.
Using two Matrix e[][] for extra spaces, l[][] for line cost.
Using two arrays t[] for total cost, s[] for solution.
Loop-1 will calculate the Extra spaces in single line.
Loop-2 will calculate the line cost with the extra spaces found.
Loop-3 will calculate the minimum solution.
Print using solution.

Begin word_wrap

Take two 2-D array or matrices for extra spaces as 'e' & for line cost as 'l' of order of (size as 'n')+1

e[n+1][n+1] and l[n+1][n+1]

Take two 1-D array for total cost as 't' & for sol. of size as 's' of (size as 'n')+1

t[n+1] and s[n+1]

loop1: for i=1 to n

{
   e[i, i] = w – ws[ i-1 ]
    inner loop: for j=( i+1 ) to n 
    {
     e[i, j] = e[i, j-1] – ws[ j-1 ] - 1
    }
  }

loop2:

for i=1 to n 
    {
        for j=( i+1 ) to n 
        {
            if e[i, j] < 0, then
              l[i, j] = INT_MAX
            else if j = n and e[i, j] >= 0, then
              l[i, j] = 0
            else
              l[i, j] = e[i, j]^2
        }
    }

t[0] = 0
loop3:

    for j = 1 to n
    {
        t[j] = INT_MAX
        for i=1 to j
        {
            if t[i-1] != INT_MAX and l[i, j] != INT_MAX and
            (t[i-1] + l[i,j] < t[j]), then
            t[i – 1] = t[i – 1] + l[i, j]     
            s[j] = i
        }
    }

print the solution matrix using solution 's'

End word_wrap

C++ Implementation of Word Wrap Problem:

#include<bits/stdc++.h>
using namespace std;

 //To print solution
int prin (int s[], int n)
{
    int f;
    if (s[n] == 1)
        f = 1;
    else
        f = prin(s, s[n]-1) + 1;
    cout<<"\nline "<<f<<"-> word no. "<<s[n]<<" to "<<n;
    return f;
}
 //Word wrap funtion
   void word_wrap (int ws[], int n, int w)
{
    int e[n+1][n+1], l[n+1][n+1];
    int t[n+1], s[n+1];
    for (int i = 1; i <= n; i++)
    {
        e[i][i] = w - ws[i-1];
        for (int j = i+1; j <= n; j++)
            e[i][j] = e[i][j-1] - ws[j-1] - 1;
    }
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            if (e[i][j] < 0)
                l[i][j] = INT_MAX;
            else if (j == n && e[i][j] >= 0)
                l[i][j] = 0;
            else
                l[i][j] = e[i][j] * e[i][j];
        }
    }
 
    t[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        t[i] = INT_MAX;
        for (int j = 1; j <= i; j++)
        {
            if (t[j-1] != INT_MAX && l[j][i] != INT_MAX &&
                           (t[j-1] + l[j][i] < t[i]))
            {
                t[i] = t[j-1] + l[j][i];
                s[i] = j;
            }
        }
    }
 
    prin(s, n);
}

int main()
{
    int ws[] = {3, 2, 4, 5};
    int n = sizeof(ws)/sizeof(int);
    int w = 6;
    word_wrap (ws, n, w);
    return 0;
}

OUTPUT:

line 1-> word no. 1 to 2
line 2-> word no. 3 to 3
line 3-> word no. 4 to 4

Complexity

Time Complexity = O(n^2), Here n^2 time complexity is coming from nested-loops, as outer loop runs from 1 to n and inner loop runs from 1 to n(approx), therefore it becomes O(n * n).

Space Complexity = O(n^2), Here extra space is a 2D array which is of space size (n * n), therefore it becomes O(n * n).

With this article at OpenGenus, you must have the complete idea of Word Wrap problem.

Word Wrap Problem

Dynamic Programming (DP) Algorithms

Table of contents: