Dada una string str y una array de enteros width[] donde:
ancho[0] = ancho del carácter ‘a’
ancho[1] = ancho del carácter ‘b’
…
ancho[25] = ancho del carácter ‘z’
La tarea es encontrar el número de líneas que tomará escribir la string str en un papel y el ancho de la última línea hasta la cual está ocupada.
Nota: El ancho de una línea es de 10 unidades .
Ejemplos:
Entrada: str = “bbbcccdddaa”,
ancho[] = {4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 1, 1, 1, 1, 1, 1}
Salida: (2, 8)
«bbbcccddd» cubrirá la primera línea (9 * 1 = 9 unidades)
Como ‘a’ tiene un ancho de 4 que no puede caber en restante 1 unidad en la primera línea.
Tendrá que ser escrito en la segunda línea.
Entonces, la siguiente línea contendrá «aa» que cubre 4 * 2 = 8 unidades.
Necesitamos 1 línea completa y una línea con un ancho de 8 unidades.
Entrada: str = “abcdefghijklmnopqrstuvwxyz”,
ancho[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 1, 1, 1, 1, 1, 1}
Salida: (3, 6)
Todos los caracteres tienen el mismo ancho de 1. Para escribir los 26 caracteres,
Necesitamos 2 líneas completas y una línea con 6 unidades de ancho.
Enfoque: Escribiremos cada carácter en la string str uno por uno. A medida que escribimos un carácter, actualizamos inmediatamente (líneas, ancho) que realiza un seguimiento de cuántas líneas hemos usado hasta ahora y cuál es la longitud del espacio usado en la última línea.
Si el ancho [char] en str se ajusta a nuestra línea actual, lo agregaremos. De lo contrario, comenzaremos con una nueva línea
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the number of lines required
pair<int, int> numberOfLines(string S, int *widths)
{
// If string is empty
if (S.empty())
return {0, 0};
// Initialize lines and width
int lines = 1, width = 0;
// Iterate through S
for (auto character : S)
{
int w = widths[character - 'a'];
width += w;
if (width >= 10)
{
lines++;
width = w;
}
}
// Return lines and width used
return {lines, width};
}
// Driver Code
int main()
{
string S = "bbbcccdddaa";
int widths[] = {4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
// Function call to print required answer
pair<int, int> ans = numberOfLines(S, widths);
cout << ans.first << " " << ans.second << endl;
return 0;
}
// This code is contributed by
// sanjeev2552
Java
// JAVA implementation of the approach
class GFG
{
// Function to return the number of lines required
static int[] numberOfLines(String S, int []widths)
{
// If String is empty
if (S.isEmpty())
return new int[]{0, 0};
// Initialize lines and width
int lines = 1, width = 0;
// Iterate through S
for (char character : S.toCharArray())
{
int w = widths[character - 'a'];
width += w;
if (width >= 10)
{
lines++;
width = w;
}
}
// Return lines and width used
return new int[]{lines, width};
}
// Driver Code
public static void main(String[] args)
{
String S = "bbbcccdddaa";
int widths[] = {4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
// Function call to print required answer
int []ans = numberOfLines(S, widths);
System.out.print(ans[0]+ " " + ans[1] +"\n");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach
# Function to return the number of lines required
def numberOfLines(S, widths):
# If string is empty
if(S == ""):
return 0, 0
# Initialize lines and width
lines, width = 1, 0
# Iterate through S
for c in S:
w = widths[ord(c) - ord('a')]
width += w
if width > 10:
lines += 1
width = w
# Return lines and width used
return lines, width
# Driver Code
S = "bbbcccdddaa"
Widths = [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
# Function call to print required answer
print(numberOfLines(S, Widths))
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the number of lines required
static int[] numberOfLines(String S, int []widths)
{
// If String is empty
if (S.Length == 0)
return new int[]{0, 0};
// Initialize lines and width
int lines = 1, width = 0;
// Iterate through S
foreach (char character in S.ToCharArray())
{
int w = widths[character - 'a'];
width += w;
if (width >= 10)
{
lines++;
width = w;
}
}
// Return lines and width used
return new int[]{lines, width};
}
// Driver Code
public static void Main(String[] args)
{
String S = "bbbcccdddaa";
int []widths = {4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
// Function call to print required answer
int []ans = numberOfLines(S, widths);
Console.Write(ans[0]+ " " + ans[1] +"\n");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JAVAscript implementation of the approach
// Function to return the number of lines required
function numberOfLines(S,widths)
{
// If String is empty
if (S.length==0)
return [0, 0];
// Initialize lines and width
let lines = 1, width = 0;
// Iterate through S
for (let character of S.split(""))
{
let w = widths[character.charCodeAt(0) - 'a'.charCodeAt(0)];
width += w;
if (width >= 10)
{
lines++;
width = w;
}
}
// Return lines and width used
return [lines, width];
}
// Driver Code
let S = "bbbcccdddaa";
let widths = [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
// Function call to print required answer
let ans = numberOfLines(S, widths);
document.write(ans[0]+ " " + ans[1] +"<br>");
// This code is contributed by rag2127
</script>
(2, 8)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA