Time and Space Complexity of Text Justification

The recursion tree for DP[0] is shown in the figure below. It shows that O(n) DP values have to be computed, where each requires at the most O(n) computations. This makes an overall time complexity of O(n${}^2$).

During the solution, we are creating 3 new arrays of the same length of words which is n. So the space complexity will be O(n).

Java Code for Text Justification

The complete Java code for text justification is given below. I am using a large positive integer to represent infinity. The public function solve can be called to determine the split as well as display the justified text. I would encourage you to experiment with the objective function to see how it affects your solution. What would happen if you take square or absolute differences instead of the cube function?

Final Words

Dynamic programming is awesome for text justification! You can look at the greedy solutions and other algorithms too. If you are looking for a quick implementation, then go for a greedy solution as it works for many cases. However, dynamic programming gives you a guarantee that the solution's objective function would be optimized for the solved arrangement of text. Your text would look pretty in the end as the spaces would be evenly distributed on all lines. I hope you enjoy solving this problem as much as I enjoyed writing about it.

xxxxxxxxxx

}

import java.util.*;

​

class dpTextJustify {

    int[] dp; //optimal obj func for index i

    int[] split; //where to split the line

    int[] len; //length of words

    int pageWidth;

    final int infValue = 1000000000;

    ArrayList < Integer > lineEnd;

​

    //main function for text justification

    public int[] solve(String[] words, int maxWidth) {

        pageWidth = maxWidth;

        dp = new int[words.length];

        split = new int[words.length];

        len = new int[words.length];

        for (int i = 0; i < words.length; ++i) {

            len[i] = words[i].length();

            dp[i] = -1; //initialize to -1

        }

        solve();

        getLines();

        int j = 0;

        for (int i = 0; i < lineEnd.size(); ++i) {

            displayLine(words, maxWidth, j, lineEnd.get(i), i == lineEnd.size() - 1);

            j = lineEnd.get(i) + 1;

            System.out.print("\n");

        }

        return split;