Movimientos mínimos necesarios para escribir una palabra en el teclado basado en QWERTY

Dada una string S que consta solo de letras minúsculas en inglés. La tarea es encontrar el número mínimo de movimientos de los dedos para escribir la string dada. El movimiento se considera cuando presiona la tecla que no está en la fila de la tecla actualmente presionada en el teclado.

Teclado QWERTY compuesto únicamente por letras en inglés.

Ejemplos:

Entrada: S = “ geeksforgeeks”
Salida: 7
Explicación:
mover 1 >> g
mover 2 >> e
mover 2 >> e
mover 3 >> k
mover 3 >> s
mover 3 >> f
mover 4 >> o
mover 4 > > r
mueve 5 >> g
mueve 6 >> e
mueve 6 >> e
mueve 7 >> k
mueve 7 >> s

Entrada: S = “radhamohan”
Salida: 6

Enfoque: Esto se puede hacer configurando inicialmente el número de fila de cada carácter en el teclado QWERTY . A continuación se muestran los pasos:

1. Almacene la fila de cada carácter en una array fila[] .
2. Inicializar mover = 1 .
3. Recorra la string dada y verifique si la fila del carácter actual en la string es igual al carácter anterior o no.
4. Si el carácter actual no es igual, incremente el movimiento ya que necesitamos cambiar la fila actual mientras imprimimos el carácter.
5. De lo contrario, verifique los siguientes pares de caracteres.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that calculates the moves
// required to print the current string
int numberMoves(string s)
{
    // row1 has qwertyuiop, row2 has
    // asdfghjkl, and row3 has zxcvbnm
    // Store the row number of
    // each character
    int row[] = { 2, 3, 3, 2, 1, 2, 2,
                  2, 1, 2, 2, 2, 3, 3,
                  1, 1, 1, 1, 2, 1, 1,
                  3, 1, 3, 1, 3 };
 
    // String length
    int n = s.length();
 
    // Initialise move to 1
    int move = 1;
 
    // Traverse the string
    for (int i = 1; i < n; i++) {
 
        // If current row number is
        // not equal to previous row
        // then increment the moves
        if (row[s[i] - 'a']
            != row[s[i - 1] - 'a']) {
            move++;
        }
    }
 
    // Return the moves
    return move;
}
 
// Driver Code
int main()
{
    // Given String str
    string str = "geeksforgeeks";
 
    // Function Call
    cout << numberMoves(str);
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
// Function that calculates the moves
// required to print the current String
static int numberMoves(String s)
{
    // row1 has qwertyuiop, row2 has
    // asdfghjkl, and row3 has zxcvbnm
    // Store the row number of
    // each character
    int row[] = { 2, 3, 3, 2, 1, 2, 2,
                  2, 1, 2, 2, 2, 3, 3,
                  1, 1, 1, 1, 2, 1, 1,
                  3, 1, 3, 1, 3 };
 
    // String length
    int n = s.length();
 
    // Initialise move to 1
    int move = 1;
 
    // Traverse the String
    for (int i = 1; i < n; i++)
    {
 
        // If current row number is
        // not equal to previous row
        // then increment the moves
        if (row[s.charAt(i) - 'a'] !=
            row[s.charAt(i-1) - 'a'])
        {
            move++;
        }
    }
 
    // Return the moves
    return move;
}
 
// Driver Code
public static void main(String[] args)
{
    // Given String str
    String str = "geeksforgeeks";
 
    // Function Call
    System.out.print(numberMoves(str));
}
}
 
// This code is contributed by sapnasingh4991

# Python3 program for the above approach
 
# Function that calculates the moves
# required to print current String
def numberMoves(s):
   
    # row1 has qwertyuiop, row2 has
    # asdfghjkl, and row3 has zxcvbnm
    # Store the row number of
    # each character
    row = [2, 3, 3, 2, 1, 2,
           2, 2, 1, 2, 2, 2, 3,
           3, 1, 1, 1, 1, 2, 1,
           1, 3, 1, 3, 1, 3];
 
    # String length
    n = len(s);
 
    # Initialise move to 1
    move = 1;
 
    # Traverse the String
    for i in range(1, n):
       
    # If current row number is
    # not equal to previous row
    # then increment the moves
    if(row[ord(s[i]) -
           ord('a')] != row[ord(s[i - 1]) -
                            ord('a')]):
      move += 1;
 
    # Return the moves
    return move;
 
# Driver Code
if __name__ == '__main__':
   
    # Given String str
    str = "geeksforgeeks";
 
    # Function Call
    print(numberMoves(str));
 
# This code is contributed by Rajput-Ji Add

// C# program for the above approach
using System;
class GFG{
 
// Function that calculates the moves
// required to print the current String
static int numberMoves(String s)
{
    // row1 has qwertyuiop, row2 has
    // asdfghjkl, and row3 has zxcvbnm
    // Store the row number of
    // each character
    int []row = { 2, 3, 3, 2, 1, 2, 2,
                  2, 1, 2, 2, 2, 3, 3,
                  1, 1, 1, 1, 2, 1, 1,
                  3, 1, 3, 1, 3 };
 
    // String length
    int n = s.Length;
 
    // Initialise move to 1
    int move = 1;
 
    // Traverse the String
    for (int i = 1; i < n; i++)
    {
 
        // If current row number is
        // not equal to previous row
        // then increment the moves
        if (row[s[i] - 'a'] !=
            row[s[i - 1] - 'a'])
        {
            move++;
        }
    }
 
    // Return the moves
    return move;
}
 
// Driver Code
public static void Main(String[] args)
{
    // Given String str
    String str = "geeksforgeeks";
 
    // Function Call
    Console.Write(numberMoves(str));
}
}
 
// This code is contributed by sapnasingh4991

7

Complejidad de tiempo: O(N), donde N es la longitud de la string.
Complejidad espacial: O(1)