Dado un diseño de teclado de string de tamaño 26 que representa la secuencia de caracteres presentes en una sola fila de un teclado y una palabra de string , la tarea es calcular el tiempo total necesario para escribir la palabra, comenzando desde la tecla 0 , si se mueve a la adyacente. llaves requiere unidad de tiempo.
Ejemplos:
Entrada: keyboardLayout = “abcdefghijklmnopqrstuvwxyz”, palabra = “perro”
Salida: 22
Explicación:
Presionar la tecla ‘d’ requiere 3 unidades de tiempo (es decir, ‘a’ -> ‘b’ -> ‘c’ -> ‘d’)
Presionar la tecla ‘o’ requiere 11 unidades de tiempo (es decir, ‘d’ -> ‘e’ -> ‘f’ -> ‘g’ -> ‘h’ -> ‘i’ -> ‘j’ -> ‘k ‘ -> ‘l’ -> ‘m’ -> ‘n’ -> ‘o’)
Presionar la tecla ‘g’ requiere 8 unidades de tiempo (es decir, ‘o’ -> ‘n’ -> ‘m’ -> ‘l’ -> ‘k’ -> ‘j’ -> ‘i’ -> ‘h’ -> ‘g’)
Por lo tanto, el tiempo total empleado = 3 + 11 + 8 = 22.Entrada: disposición del teclado = “abcdefghijklmnopqrstuvwxyz”, palabra = “abcdefghijklmnopqrstuvwxyz”
Salida: 25
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice un vector , digamos pos, para almacenar la posición de todos los caracteres.
- Inicialice dos variables, digamos last , para almacenar el último índice actualizado y result, para almacenar el tiempo total que se tarda en escribir la palabra.
- Iterar sobre los caracteres de la palabra de string :
- Inicialice dos variables, digamos destino, para almacenar el índice del siguiente carácter que se requiere escribir, y distancia , para almacenar la distancia de ese índice desde el índice actual.
- Agregue el valor de la distancia al resultado .
- Actualice el último a destino .
- Después de completar las operaciones anteriores, imprima el valor del resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate time
// taken to type the given word
int timeTakenToType(string& keyboardLayout,
string& word)
{
// Stores position of characters
vector<int> pos(26);
// Iterate over the range [0, 26]
for (int i = 0; i < 26; ++i) {
// Set position of each character
char ch = keyboardLayout[i];
pos[ch - 'a'] = i;
}
// Store the last index
int last = 0;
// Stores the total time taken
int result = 0;
// Iterate over the characters of word
for (int i = 0; i < (int)word.size(); ++i) {
char ch = word[i];
// Stores index of the next character
int destination = pos[ch - 'a'];
// Stores the distance of current
// character from the next character
int distance = abs(destination - last);
// Update the result
result += distance;
// Update last position
last = destination;
}
// Print the result
cout << result;
}
// Driver Code
int main()
{
// Given keyboard layout
string keyboardLayout
= "acdbefghijlkmnopqrtsuwvxyz";
// Given word
string word = "dog";
// Function call to find the minimum
// time required to type the word
timeTakenToType(keyboardLayout, word);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to calculate time
// taken to type the given word
static void timeTakenToType(String keyboardLayout,
String word)
{
// Stores position of characters
int[] pos = new int[26];
// Iterate over the range [0, 26]
for (int i = 0; i < 26; i++) {
// Set position of each character
char ch = keyboardLayout.charAt(i);
pos[ch - 'a'] = i;
}
// Store the last index
int last = 0;
// Stores the total time taken
int result = 0;
// Iterate over the characters of word
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
// Stores index of the next character
int destination = pos[ch - 'a'];
// Stores the distance of current
// character from the next character
int distance = Math.abs(destination - last);
// Update the result
result += distance;
// Update last position
last = destination;
}
System.out.println(result);
}
// Driver Code
public static void main(String[] args)
{
// Given keyboard layout
String keyboardLayout
= "acdbefghijlkmnopqrtsuwvxyz";
// Given word
String word = "dog";
// Function call to find the minimum
// time required to type the word
timeTakenToType(keyboardLayout, word);
}
}
// This code is contributed by aadityapburujwale.
Python3
# Python3 program for the above approach
# Function to calculate time
# taken to type the given word
def timeTakenToType(keyboardLayout, word):
# Stores position of characters
pos = [0]*(26)
# Iterate over the range [0, 26]
for i in range(26):
# Set position of each character
ch = keyboardLayout[i]
pos[ord(ch) - ord('a')] = i
# Store the last index
last = 0
# Stores the total time taken
result = 0
# Iterate over the characters of word
for i in range(len(word)):
ch = word[i]
# Stores index of the next character
destination = pos[ord(ch) - ord('a')]
# Stores the distance of current
# character from the next character
distance = abs(destination - last)
# Update the result
result += distance
# Update last position
last = destination
# Print result
print (result)
# Driver Code
if __name__ == '__main__':
# Given keyboard layout
keyboardLayout = "acdbefghijlkmnopqrtsuwvxyz"
# Given word
word = "dog"
# Function call to find the minimum
# time required to type the word
timeTakenToType(keyboardLayout, word)
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
public class GFG {
// Function to calculate time
// taken to type the given word
static void timeTakenToType(String keyboardLayout,
String word)
{
// Stores position of characters
int[] pos = new int[26];
// Iterate over the range [0, 26]
for (int i = 0; i < 26; i++) {
// Set position of each character
char ch = keyboardLayout[i];
pos[ch - 'a'] = i;
}
// Store the last index
int last = 0;
// Stores the total time taken
int result = 0;
// Iterate over the characters of word
for (int i = 0; i < word.Length; i++) {
char ch = word[i];
// Stores index of the next character
int destination = pos[ch - 'a'];
// Stores the distance of current
// character from the next character
int distance = Math.Abs(destination - last);
// Update the result
result += distance;
// Update last position
last = destination;
}
Console.WriteLine(result);
}
// Driver Code
public static void Main(String[] args)
{
// Given keyboard layout
String keyboardLayout
= "acdbefghijlkmnopqrtsuwvxyz";
// Given word
String word = "dog";
// Function call to find the minimum
// time required to type the word
timeTakenToType(keyboardLayout, word);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Function to calculate time
// taken to type the given word
function timeTakenToType(keyboardLayout, word)
{
// Stores position of characters
var pos = Array(26).fill(0);
// Iterate over the range [0, 26]
for(var i = 0; i < 26; ++i)
{
// Set position of each character
var ch = keyboardLayout[i];
pos[ch.charCodeAt(0) -
'a'.charCodeAt(0)] = i;
}
// Store the last index
var last = 0;
// Stores the total time taken
var result = 0;
// Iterate over the characters of word
for(var i = 0; i < word.length; ++i)
{
var ch = word[i];
// Stores index of the next character
var destination = pos[ch.charCodeAt(0) -
'a'.charCodeAt(0)];
// Stores the distance of current
// character from the next character
var distance = Math.abs(destination - last);
// Update the result
result += distance;
// Update last position
last = destination;
}
// Print the result
document.write(result);
}
// Driver Code
// Given keyboard layout
var keyboardLayout = "acdbefghijlkmnopqrtsuwvxyz";
// Given word
var word = "dog";
// Function call to find the minimum
// time required to type the word
timeTakenToType(keyboardLayout, word);
// This code is contributed by rutvik_56
</script>
Producción
22
Complejidad de tiempo: O(N), donde N es el tamaño de la palabra de la string.
Espacio Auxiliar: O(1)