Dada una string str y el ancho de cada línea como L , la tarea es justificar la string de modo que cada línea de texto justificado tenga una longitud L con la ayuda del espacio (‘ ‘) y la última línea debe estar justificada a la izquierda.
Ejemplos:
Entrada: str = «GeeksforGeek es el mejor portal de informática para geeks»., L = 16
Salida:
GeeksforGeek__es
el_________mejor portal de
informática
_______para
geeks.__________Entrada: str = “El veloz zorro marrón salta sobre el perro perezoso.”, L = 11
Salida:
El___veloz__zorro
marrón saltó_sobre
los____perros
perezosos
.______
El símbolo _ denota un espacio.
Enfoque:
el número de espacios entre palabras en cada línea no se puede calcular hasta que se conozca un conjunto completo de palabras en esa línea. Resolveremos este problema línea por línea.
- Dividir el texto dado en palabras
- En primer lugar, seleccione las palabras que se pueden insertar en cada línea, incluyendo un espacio entre cada palabra. Para eso, la suma de las longitudes de las palabras incluidas con un espacio entre ellas debe ser menor o igual a L .
- Ahora cuente el número de espacios necesarios para hacer que la longitud de cada línea sea L y distribuya los espacios de manera uniforme.
- Repita los pasos anteriores para el siguiente grupo de palabras.
- Para la última línea se deben asignar espacios al final ya que la última línea debe estar justificada a la izquierda .
A continuación se muestra la implementación del enfoque anterior:
// C++ program to Justify the given Text
// according to the given width of each line
#include "bits/stdc++.h"
using namespace std;
// Function to join the words
// with spaces spread evenly
string JoinALineWithSpace(
vector<string>& words,
int start, int end,
int num_spaces)
{
// Number of words in current line
int num_words_curr_line
= end - start + 1;
// String to store the justified text
string line;
for (int i = start; i < end; i++) {
line += words[i];
--num_words_curr_line;
// Count number of current space needed
int num_curr_space
= ceil((double)(num_spaces)
/ num_words_curr_line);
// Insert spaces in string line
line.append(num_curr_space, ' ');
// Delete the spaces inserted in line
num_spaces -= num_curr_space;
}
// Insert word to string line
line += words[end];
line.append(num_spaces, ' ');
// Return justified text
return line;
}
// Function that justify the words of
// sentence of length of line L
vector<string> JustifyText(
vector<string>& words,
int L)
{
int curr_line_start = 0;
int num_words_curr_line = 0;
int curr_line_length = 0;
// To store the justified text
vector<string> result;
// Traversing the words array
for (int i = 0; i < words.size(); i++) {
// curr_line_start is the first word
// in the current line, and i is
// used to identify the last word
++num_words_curr_line;
int lookahead_line_length
= curr_line_length
+ words[i].size()
+ (num_words_curr_line - 1);
// If by including the words length becomes L,
// then that set of words is justified
// and add the justified text to result
if (lookahead_line_length == L) {
// Justify the set of words
string ans
= JoinALineWithSpace(
words,
curr_line_start,
i,
i - curr_line_start);
// Store the justified text in result
result.emplace_back(ans);
// Start the current line
// with next index
curr_line_start = i + 1;
// num of words in the current line
// and current line length set to 0
num_words_curr_line = 0;
curr_line_length = 0;
}
// If by including the words such that
// length of words becomes greater than L,
// then hat set is justified with
// one less word and add the
// justified text to result
else if (lookahead_line_length > L) {
// Justify the set of words
string ans
= JoinALineWithSpace(
words,
curr_line_start,
i - 1,
L - curr_line_length);
// Store the justified text in result
result.emplace_back(ans);
// Current line set to current word
curr_line_start = i;
// Number of words set to 1
num_words_curr_line = 1;
// Current line length set
// to current word length
curr_line_length = words[i].size();
}
// If length is less than L then,
// add the word to current line length
else {
curr_line_length
+= words[i].size();
}
}
// Last line is to be left-aligned
if (num_words_curr_line > 0) {
string line
= JoinALineWithSpace(
words,
curr_line_start,
words.size() - 1,
num_words_curr_line - 1);
line.append(
L - curr_line_length
- (num_words_curr_line - 1),
' ');
// Insert the last line
// left-aligned to result
result.emplace_back(line);
}
// Return result
return result;
}
// Function to insert words
// of sentence
vector<string> splitWords(string str)
{
vector<string> words;
string a = "";
for (int i = 0; str[i]; i++) {
// Add char to string a
// to get the word
if (str[i] != ' ') {
a += str[i];
}
// If a space occurs
// split the words and
// add it to vector
else {
words.push_back(a);
a = "";
}
}
// Push_back the last word
// of sentence
words.push_back(a);
// Return the vector of
// words extracted from
// string
return words;
}
// Function to print justified text
void printJustifiedText(vector<string>& result)
{
for (auto& it : result) {
cout << it << endl;
}
}
// Function to call the justification
void justifyTheText(string str, int L)
{
vector<string> words;
// Inserting words from
// given string
words = splitWords(str);
// Function call to
// justify the text
vector<string> result
= JustifyText(words, L);
// Print the justified
// text
printJustifiedText(result);
}
// Driver Code
int main()
{
string str
= "GeeksforGeek is the best"
" computer science portal"
" for geeks.";
int L = 16;
justifyTheText(str, L);
return 0;
}
Producción:
GeeksforGeek is the best computer science portal for geeks.
Complejidad de tiempo: O(N), donde N = longitud de la string