This Java program Implements Word Wrap Problem.A 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.
Here is the source code of the Java Program to Implement Word Wrap Problem.The Java program is successfully compiled and run on a Linux system. The program output is also shown below.
public class WordWrapProblem
{
private static final int INFINITY = Integer.MAX_VALUE;
void solveWordWrap(int l[], int n, int M)
{
int extras[][] = new int[n + 1][n + 1];
int lineCost[][] = new int[n + 1][n + 1];
int cost[] = new int[n + 1];
int printSol[] = new int[n + 1];
int i, j;
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;
}
}
for (i = 1; i <= n; i++)
{
for (j = i; j <= n; j++)
{
if (extras[i][j] < 0)
{
lineCost[i][j] = INFINITY;
} else if (j == n && extras[i][j] >= 0)
{
lineCost[i][j] = 0;
} else
lineCost[i][j] = extras[i][j] * extras[i][j];
}
}
cost[0] = 0;
for (j = 1; j <= n; j++)
{
cost[j] = INFINITY;
for (i = 1; i <= j; i++)
{
if (cost[i - 1] != INFINITY && lineCost[i][j] != INFINITY
&& (cost[i - 1] + lineCost[i][j] < cost[j]))
{
cost[j] = cost[i - 1] + lineCost[i][j];
printSol[j] = i;
}
}
}
printSolution(printSol, n);
}
private int printSolution(int p[], int n)
{
int k;
if (p[n] == 1)
{
k = 1;
} else
{
k = printSolution(p, p[n] - 1) + 1;
}
System.out.println("Line number " + k + " From word no " + p[n] + " to " + n);
return k;
}
public static void main(String...arg)
{
int l[] = {3,2,2,5};
int n = 4;
int M = 6;
WordWrapProblem wordWrapProblem = new WordWrapProblem();
wordWrapProblem.solveWordWrap(l, n, M);
}
}
$ javac WordWrapProblem.java $ java WordWrapProblem 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
Related posts:
Java Program to Implement Pollard Rho Algorithm
Java Program to Find Inverse of a Matrix
Sorting Query Results with Spring Data
Spring MVC Async vs Spring WebFlux
Java Program to Implement Multi-Threaded Version of Binary Search Tree
Java Program to Implement Stack using Two Queues
Java Program to Implement AttributeList API
Java Program to Implement Euler Circuit Problem
Converting a Stack Trace to a String in Java
Introduction to Liquibase Rollback
Java Program to Check if a Given Set of Three Points Lie on a Single Line or Not
Multipart Upload with HttpClient 4
Explain about URL and HTTPS protocol
Spring WebClient Requests with Parameters
Different Ways to Capture Java Heap Dumps
Spring Security Logout
Spring Boot - Enabling HTTPS
Quick Guide to the Java StringTokenizer
Java Program to Find the GCD and LCM of two Numbers
Java Program to Implement Expression Tree
Java Program to Implement Strassen Algorithm
Java Program to Implement Control Table
Spring Data MongoDB Transactions
Validations for Enum Types
Find the Registered Spring Security Filters
Using a Custom Spring MVC’s Handler Interceptor to Manage Sessions
Hướng dẫn Java Design Pattern – Iterator
Enum trong java
Introduction to Spring Security Expressions
A Guide to Queries in Spring Data MongoDB
Getting Started with GraphQL and Spring Boot
Java Program to Solve the Fractional Knapsack Problem