Text Justification Algorithm

Question

This is a very famous problem in DP, Can somebody help to visualize the recursion part of it.How are the Permutations or Combinations will be generated.

problem reference. https://www.geeksforgeeks.org/dynamic-programming-set-18-word-wrap/

Answer 1

Given the maximum line width as L, the idea to justify the Text T, is to consider all suffixes of the Text (consider words instead of characters for forming suffixes to be precise.) Dynamic Programming is nothing but "Careful Brute-force". If you consider the brute force approach, you need to do the following.

1. consider putting 1, 2, .. n words in the first line.
2. for each case described in case 1(say i words are put in line 1), consider cases of putting 1, 2, .. n -i words in the second line and then remaining words on third line and so on..

Instead lets just consider the problem to find out the cost of putting a word at the beginning of a line. In general we can define DP(i) to be the cost for considering (i- 1)th word as the beginning of a Line.

How can we form a recurrence relation for DP(i)?

If jth word is the beginning of the next line, then the current line will contain words[i:j) (j exclusive) and the cost of jth word being the beginning of the next line will be DP(j). Hence DP(i) = DP(j) + cost of putting words[i:j) in the current line As we want to minimise the total cost, DP(i) can be defined as follows.

Recurrence relation:

DP(i) = min { DP(j) + cost of putting words[i:j in the current line } for all j in [i+1, n]

Note j = n signify that no words are left to be put in the next line.

The base Case: DP(n) = 0 => at this point there is no word left to be written.

To summarise:

1. Subproblems: suffixes , words[:i]
2. Guess: Where to start the next line, # of choices n - i -> O(n)
3. Recurrence: DP(i) = min {DP(j) + cost of putting words[i:j) in the current line } If we use memoization, the expression inside the curly brace should should take O(1) time, and the loop run O(n) times (# of choices times). i Varies from n down to 0 => Hence total complexity is brought down to O(n^2).

Now even though we derived the minimum cost for justifying the text, we also need to solve the original problem by keeping track of the j value for chosen as minimum in the above expression, so that we can later use the same to print out the justified text. The idea is of keeping parent pointer.

Hope this helps you understand the solution. Below is the simple implementation of the above idea.

 public class TextJustify {
    class IntPair {
        //The cost or badness
        final int x;

        //The index of word at the beginning of a line
        final int y;
        IntPair(int x, int y) {this.x=x;this.y=y;}
    }
    public List<String> fullJustify(String[] words, int L) {
        IntPair[] memo = new IntPair[words.length + 1];

        //Base case
        memo[words.length] = new IntPair(0, 0);


        for(int i = words.length - 1; i >= 0; i--) {
            int score = Integer.MAX_VALUE;
            int nextLineIndex = i + 1;
            for(int j = i + 1; j <= words.length; j++) {
                int badness = calcBadness(words, i, j, L);
                if(badness < 0 || badness == Integer.MAX_VALUE) break;
                int currScore = badness + memo[j].x;
                if(currScore < 0 || currScore == Integer.MAX_VALUE) break;
                if(score > currScore) {
                    score = currScore;
                    nextLineIndex = j;
                }
            }
            memo[i] = new IntPair(score, nextLineIndex);
        }

        List<String> result = new ArrayList<>();
        int i = 0;
        while(i < words.length) {
            String line = getLine(words, i, memo[i].y);
            result.add(line);
            i = memo[i].y;
        }
        return result;
    }

    private int calcBadness(String[] words, int start, int end, int width) {
        int length = 0;
        for(int i = start; i < end; i++) {
            length += words[i].length();
            if(length > width) return Integer.MAX_VALUE;
            length++;
        }
        length--;
        int temp = width - length;
        return temp * temp;
    }


    private String getLine(String[] words, int start, int end) {
        StringBuilder sb = new StringBuilder();
        for(int i = start; i < end - 1; i++) {
            sb.append(words[i] + " ");
        }
        sb.append(words[end - 1]);

        return sb.toString();
    }
  }