Word Wrap Problem
Given an array words[] of size n, where words[i] denotes the number of characters in one word. Let K be the 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. When line breaks are inserted there is a possibility that extra spaces are present in each line. The extra spaces include spaces put at the end of every line except the last one.
The task is to minimize the following total cost where total cost = Sum of cost of all lines, where the cost of the line is = (Number of extra spaces in the line)2.
Example:
Input: words = {3,2,2,5}, k = 6
Output: 10
Explanation: Given a line can have 6 characters,
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
So total cost = (6-3)2 + (6-2-2-1)2 = 32+12 = 10.Input: words = {3,2,2}, k = 4
Output: 5
Explanation: Given a line can have 4 characters,
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
Same explaination as above total cost = (4 – 3)2 + (4 – 2)2 = 5.
Word Wrap Problem with Memoization:
The problem can be solved using a divide and conquer (recursive) approach. The algorithm for the same is mentioned below:
- We recur for each word starting with first word, and remaining length of the line (initially k).
- The last word would be the base case: We check if we can put it on same line:
- if yes, then we return cost as 0.
- if no, we return cost of current line based on its remaining length.
- For non-last words, we have to check if it can fit in the current line:
- If yes, then we have two choices i.e. whether to put it in same line or next line.
- if we put it on next line: cost1 = square(remLength) + cost of putting word on next line.
- if we put it on same line: cost2 = cost of putting word on same line.
- return min(cost1, cost2)
- If no, then we have to put it on next line and return cost of putting word on next line
- If yes, then we have two choices i.e. whether to put it in same line or next line.
- Use memoization table of size n (number of words) * k (line length), to keep track of already visited positions.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h> using namespace std; int solveWordWrapUsingMemo( int words[], int n, int length, int wordIndex, int remLength, vector<vector< int > > memo); int square( int n) { return n * n; } int solveWordWrapUtil( int words[], int n, int length, int wordIndex, int remLength, vector<vector< int > > memo) { // base case for last word if (wordIndex == n - 1) { memo[wordIndex][remLength] = words[wordIndex] < remLength ? 0 : square(remLength); return memo[wordIndex][remLength]; } int currWord = words[wordIndex]; // if word can fit in the remaining line if (currWord < remLength) { return min(solveWordWrapUsingMemo( words, n, length, wordIndex + 1, remLength == length ? remLength - currWord : remLength - currWord - 1, memo), square(remLength) + solveWordWrapUsingMemo( words, n, length, wordIndex + 1, length - currWord, memo)); } else { // if word is kept on next line return square(remLength) + solveWordWrapUsingMemo( words, n, length, wordIndex + 1, length - currWord, memo); } } int solveWordWrapUsingMemo( int words[], int n, int length, int wordIndex, int remLength, vector<vector< int > > memo) { if (memo[wordIndex][remLength] != -1) { return memo[wordIndex][remLength]; } memo[wordIndex][remLength] = solveWordWrapUtil( words, n, length, wordIndex, remLength, memo); return memo[wordIndex][remLength]; } int solveWordWrap( int words[], int n, int k) { vector<vector< int > > memo(n, vector< int >(k + 1, -1)); return solveWordWrapUsingMemo(words, n, k, 0, k, memo); } int main() { int words[] = { 3, 2, 2, 5 }; int n = sizeof (words) / sizeof (words[0]); int k = 6; cout << solveWordWrap(words, n, k); return 0; } /* This Code is contributed by Tapesh (tapeshdua420) */ |
Java
/*package whatever //do not write package name here */ import java.io.*; import java.util.Arrays; public class WordWrapDpMemo { private int solveWordWrap( int [] nums, int k) { int [][] memo = new int [nums.length][k + 1 ]; for ( int i = 0 ; i < nums.length; i++) { Arrays.fill(memo[i], - 1 ); } return solveWordWrapUsingMemo(nums, nums.length, k, 0 , k, memo); } private int solveWordWrap( int [] words, int n, int length, int wordIndex, int remLength, int [][] memo) { //base case for last word if (wordIndex == n - 1 ) { memo[wordIndex][remLength] = words[wordIndex] < remLength ? 0 : square(remLength); return memo[wordIndex][remLength]; } int currWord = words[wordIndex]; //if word can fit in the remaining line if (currWord < remLength) { return Math.min( //if word is kept on same line solveWordWrapUsingMemo(words, n, length, wordIndex + 1 , remLength == length ? remLength - currWord : remLength - currWord - 1 , memo), //if word is kept on next line square(remLength) + solveWordWrapUsingMemo(words, n, length, wordIndex + 1 , length - currWord, memo) ); } else { //if word is kept on next line return square(remLength) + solveWordWrapUsingMemo(words, n, length, wordIndex + 1 , length - currWord, memo); } } private int solveWordWrapUsingMemo( int [] words, int n, int length, int wordIndex, int remLength, int [][] memo) { if (memo[wordIndex][remLength] != - 1 ) { return memo[wordIndex][remLength]; } memo[wordIndex][remLength] = solveWordWrap(words, n, length, wordIndex, remLength, memo); return memo[wordIndex][remLength]; } private int square( int n) { return n * n; } public static void main(String[] args) { System.out.println( new WordWrapDpMemo().solveWordWrap( new int []{ 3 , 2 , 2 , 5 }, 6 )); } } |
Python3
# Python program for the above approach def square(n) : return n * n def solveWordWrapUtil(words, n, length, wordIndex, remLength, memo) : # base case for last word if (wordIndex = = n - 1 ) : memo[wordIndex][remLength] = 0 if (words[wordIndex] < remLength) else square(remLength) return memo[wordIndex][remLength] currWord = words[wordIndex] # if word can fit in the remaining line if (currWord < remLength) : return min (solveWordWrapUsingMemo( words, n, length, wordIndex + 1 , remLength - currWord if (remLength = = length) else remLength - currWord - 1 , memo), square(remLength) + solveWordWrapUsingMemo( words, n, length, wordIndex + 1 , length - currWord, memo)) else : # if word is kept on next line return (square(remLength) + solveWordWrapUsingMemo( words, n, length, wordIndex + 1 , length - currWord, memo)) def solveWordWrapUsingMemo(words, n, length, wordIndex, remLength, memo) : if (memo[wordIndex][remLength] ! = - 1 ) : return memo[wordIndex][remLength] memo[wordIndex][remLength] = (solveWordWrapUtil( words, n, length, wordIndex, remLength, memo)) return memo[wordIndex][remLength] def solveWordWrap(words, n, k) : memo = [[ 10 ] * (k + 1 )] * n return solveWordWrapUsingMemo(words, n, k, 0 , k, memo) # Driver Code if __name__ = = "__main__" : words = [ 3 , 2 , 2 , 5 ] n = len (words) k = 6 print (solveWordWrap(words, n, k)) # This code is contributed by sanjoy_62. |
C#
/*package whatever //do not write package name here */ using System; using System.Collections.Generic; public class WordWrapDpMemo { private int solveWordWrap( int [] nums, int k) { int [,] memo = new int [nums.Length ,k + 1]; for ( int i = 0; i < memo.GetLength(0); i++) { for ( int j = 0; j < memo.GetLength(1); j++) memo[i, j] = -1; } return solveWordWrapUsingMemo(nums, nums.Length, k, 0, k, memo); } private int solveWordWrap( int [] words, int n, int length, int wordIndex, int remLength, int [,] memo) { // base case for last word if (wordIndex == n - 1) { memo[wordIndex, remLength] = words[wordIndex] < remLength ? 0 : square(remLength); return memo[wordIndex, remLength]; } int currWord = words[wordIndex]; // if word can fit in the remaining line if (currWord < remLength) { return Math.Min( // if word is kept on same line solveWordWrapUsingMemo(words, n, length, wordIndex + 1, remLength == length ? remLength - currWord : remLength - currWord - 1, memo), // if word is kept on next line square(remLength) + solveWordWrapUsingMemo(words, n, length, wordIndex + 1, length - currWord, memo)); } else { // if word is kept on next line return square(remLength) + solveWordWrapUsingMemo(words, n, length, wordIndex + 1, length - currWord, memo); } } private int solveWordWrapUsingMemo( int [] words, int n, int length, int wordIndex, int remLength, int [,] memo) { if (memo[wordIndex,remLength] != -1) { return memo[wordIndex,remLength]; } memo[wordIndex,remLength] = solveWordWrap(words, n, length, wordIndex, remLength, memo); return memo[wordIndex, remLength]; } private int square( int n) { return n * n; } public static void Main(String[] args) { Console.WriteLine( new WordWrapDpMemo(). solveWordWrap( new int [] { 3, 2, 2, 5 }, 6)); } } // This code is contributed by gauravrajput1 |
Javascript
<script> /*package whatever //do not write package name here */ function solveWordWrap(nums , k) { var memo = Array(nums.length).fill().map(()=>Array(k + 1).fill(-1)); return solveWordWrapUsingMemo(nums, nums.length, k, 0, k, memo); } function solveWordWrap1(words , n , length , wordIndex , remLength, memo) { // base case for last word if (wordIndex == n - 1) { memo[wordIndex][remLength] = words[wordIndex] < remLength ? 0 : square(remLength); return memo[wordIndex][remLength]; } var currWord = words[wordIndex]; // if word can fit in the remaining line if (currWord < remLength) { return Math.min( // if word is kept on same line solveWordWrapUsingMemo(words, n, length, wordIndex + 1, remLength == length ? remLength - currWord : remLength - currWord - 1, memo), // if word is kept on next line square(remLength) + solveWordWrapUsingMemo(words, n, length, wordIndex + 1, length - currWord, memo)); } else { // if word is kept on next line return square(remLength) + solveWordWrapUsingMemo(words, n, length, wordIndex + 1, length - currWord, memo); } } function solveWordWrapUsingMemo(words , n , length , wordIndex , remLength, memo) { //if (memo[wordIndex][remLength] != -1) { // return memo[wordIndex][remLength]; //} memo[wordIndex][remLength] = solveWordWrap1(words, n, length, wordIndex, remLength, memo); return memo[wordIndex][remLength]; } function square(n) { return n * n; } var arr = [ 3, 2, 2, 5 ]; document.write(solveWordWrap(arr, 6)); // This code is contributed by gauravrajput1 </script> |
10
Time Complexity: O(n*k), where n is the number of words and k is the maximum line width. This is because the program computes the solution to each subproblem once and stores the result in the memoization table, so each subproblem is only solved once. Since there are nk subproblems, the overall time complexity is O(n*k).
Auxiliary Space: O(n*k), because the memoization table is a 2D array with n rows and k+1 columns.
Refer to the below article for space optimized approach:
Contact Us