Dada una array de strings arr[] , que consta de strings compuestas de letras minúsculas y mayúsculas, la tarea es imprimir todas las strings de la array dada que se pueden escribir usando las teclas de una sola fila de un teclado QWERTY .
Ejemplos:
Entrada: arr[] = {“Yeti”, “Had”, “GFG”, “comment”}
Salida: Yeti Had GFG
Explicación:
“Yeti” se puede escribir desde la primera fila.
“Tenía” se puede escribir desde la 2ª fila.
“GFG” se puede escribir desde la 2ª fila.
Por lo tanto, la salida requerida es Yeti Had GFG .Entrada: arr[] = {“Geeks”, “for”, “Geeks”, “Pro”}
Salida: Pro
Enfoque: El problema se puede resolver usando Hashing . La idea es recorrer la array y, para cada string, verificar si todos los caracteres de la string se pueden escribir usando las teclas de la misma fila o no. Imprime las strings para las que se encuentra que es cierto. Siga los pasos a continuación para resolver el problema:
- Inicialice un Map , digamos mp , para almacenar para cada carácter, el número de fila en el teclado en el que está presente la tecla para ese carácter.
- Recorra la array y para cada string, verifique si todos los caracteres de la string tienen el mismo número de fila asignado en el Mapa o no. Si se encuentra que es cierto, imprima la string.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print all strings that
// can be typed using keys of a single
// row in a QWERTY Keyboard
void findWordsSameRow(vector<string>& arr)
{
// Stores row number of all possible
// character of the strings
unordered_map<char, int> mp{
{ 'q', 1 }, { 'w', 1 }, { 'e', 1 }, { 'r', 1 },
{ 't', 1 }, { 'y', 1 }, { 'u', 1 }, { 'o', 1 },
{ 'p', 1 }, { 'i', 1 }, { 'a', 2 }, { 's', 2 },
{ 'd', 2 }, { 'f', 2 }, { 'g', 2 }, { 'h', 2 },
{ 'j', 2 }, { 'k', 2 }, { 'l', 2 }, { 'z', 3 },
{ 'x', 3 }, { 'c', 3 }, { 'v', 3 }, { 'b', 3 },
{ 'n', 3 }, { 'm', 3 }
};
// Traverse the array
for (auto word : arr) {
// If current string is
// not an empty string
if (!word.empty()) {
// Sets true / false if a string
// can be typed using keys of a
// single row or not
bool flag = true;
// Stores row number of the first
// character of current string
int rowNum
= mp[tolower(word[0])];
// Stores length of word
int M = word.length();
// Traverse current string
for (int i = 1; i < M; i++) {
// If current character can't be
// typed using keys of rowNum only
if (mp[tolower(word[i])]
!= rowNum) {
// Update flag
flag = false;
break;
}
}
// If current string can be typed
// using keys from rowNum only
if (flag) {
// Print the string
cout << word << " ";
}
}
}
}
// Driver Code
int main()
{
vector<string> words
= { "Yeti", "Had",
"GFG", "comment" };
findWordsSameRow(words);
}
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to print all strings that
// can be typed using keys of a single
// row in a QWERTY Keyboard
static void findWordsSameRow(List<String> arr)
{
// Stores row number of all possible
// character of the strings
Map<Character,
Integer> mp = new HashMap<Character,
Integer>();
mp.put('q', 1);
mp.put('w', 1);
mp.put('e', 1);
mp.put('r', 1);
mp.put('t', 1);
mp.put('y', 1);
mp.put('u', 1);
mp.put('i', 1);
mp.put('o', 1);
mp.put('p', 1);
mp.put('a', 2);
mp.put('s', 2);
mp.put('d', 2);
mp.put('f', 2);
mp.put('g', 2);
mp.put('h', 2);
mp.put('j', 2);
mp.put('k', 2);
mp.put('l', 2);
mp.put('z', 3);
mp.put('x', 3);
mp.put('c', 3);
mp.put('v', 3);
mp.put('b', 3);
mp.put('n', 3);
mp.put('m', 3);
// Traverse the array
for(String word : arr)
{
// If current string is
// not an empty string
if (word.length() != 0)
{
// Sets true / false if a string
// can be typed using keys of a
// single row or not
boolean flag = true;
// Stores row number of the first
// character of current string
int rowNum = mp.get(
Character.toLowerCase(word.charAt(0)));
// Stores length of word
int M = word.length();
// Traverse current string
for(int i = 1; i < M; i++)
{
// If current character can't be
// typed using keys of rowNum only
if (mp.get(Character.toLowerCase(
word.charAt(i))) != rowNum)
{
// Update flag
flag = false;
break;
}
}
// If current string can be typed
// using keys from rowNum only
if (flag)
{
// Print the string
System.out.print(word + " ");
}
}
}
}
// Driver Code
public static void main(String[] args)
{
List<String> words = Arrays.asList(
"Yeti", "Had", "GFG", "comment" );
findWordsSameRow(words);
}
}
// This code is contributed by jithin
Python3
# Python3 program to implement
# the above approach
# Function to print all strings that
# can be typed using keys of a single
# row in a QWERTY Keyboard
def findWordsSameRow(arr):
# Stores row number of all possible
# character of the strings
mp = { 'q' : 1, 'w' : 1, 'e' : 1, 'r' : 1,
't' : 1, 'y' : 1, 'u' : 1, 'o' : 1,
'p' : 1, 'i' : 1, 'a' : 2, 's' : 2,
'd' : 2, 'f' : 2, 'g' : 2, 'h' : 2,
'j' : 2, 'k' : 2, 'l' : 2, 'z' : 3,
'x' : 3, 'c' : 3, 'v' : 3, 'b' : 3,
'n' : 3, 'm' : 3 }
# Traverse the array
for word in arr:
# If current string is
# not an empty string
if (len(word) != 0):
# Sets true / false if a string
# can be typed using keys of a
# single row or not
flag = True
rowNum = mp[word[0].lower()]
# Stores length of word
M = len(word)
# Traverse current string
for i in range(1, M):
# If current character can't be
# typed using keys of rowNum only
if (mp[word[i].lower()] != rowNum):
# Update flag
flag = False
break
# If current string can be typed
# using keys from rowNum only
if (flag):
# Print the string
print(word, end = ' ')
# Driver Code
words = [ "Yeti", "Had", "GFG", "comment" ]
findWordsSameRow(words)
# This code is contributed by avanitrachhadiya2155
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to print all strings that
// can be typed using keys of a single
// row in a QWERTY Keyboard
static void findWordsSameRow(List<string> arr)
{
// Stores row number of all possible
// character of the strings
Dictionary<char,
int> mp = new Dictionary<char,
int>();
mp.Add('q', 1);
mp.Add('w', 1);
mp.Add('e', 1);
mp.Add('r', 1);
mp.Add('t', 1);
mp.Add('y', 1);
mp.Add('u', 1);
mp.Add('i', 1);
mp.Add('o', 1);
mp.Add('p', 1);
mp.Add('a', 2);
mp.Add('s', 2);
mp.Add('d', 2);
mp.Add('f', 2);
mp.Add('g', 2);
mp.Add('h', 2);
mp.Add('j', 2);
mp.Add('k', 2);
mp.Add('l', 2);
mp.Add('z', 3);
mp.Add('x', 3);
mp.Add('c', 3);
mp.Add('v', 3);
mp.Add('b', 3);
mp.Add('n', 3);
mp.Add('m', 3);
// Traverse the array
foreach(string word in arr)
{
// If current string is
// not an empty string
if (word.Length != 0)
{
// Sets true / false if a string
// can be typed using keys of a
// single row or not
bool flag = true;
// Stores row number of the first
// character of current string
int rowNum = mp[ char.ToLower(word[0])];
// Stores length of word
int M = word.Length;
// Traverse current string
for(int i = 1; i < M; i++)
{
// If current character can't be
// typed using keys of rowNum only
if (mp[Char.ToLower(word[i])] != rowNum)
{
// Update flag
flag = false;
break;
}
}
// If current string can be typed
// using keys from rowNum only
if (flag)
{
// Print the string
Console.Write(word + " ");
}
}
}
}
// Driver Code
public static void Main(String[] args)
{
List<string> words = new List<string>( new string[] {
"Yeti", "Had", "GFG", "comment" });
findWordsSameRow(words);
}
}
// This code is contributed by chitranayal
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to print all strings that
// can be typed using keys of a single
// row in a QWERTY Keyboard
function findWordsSameRow(arr) {
// Stores row number of all possible
// character of the strings
var mp = {};
mp["q"] = 1;
mp["w"] = 1;
mp["e"] = 1;
mp["r"] = 1;
mp["t"] = 1;
mp["y"] = 1;
mp["u"] = 1;
mp["i"] = 1;
mp["o"] = 1;
mp["p"] = 1;
mp["a"] = 2;
mp["s"] = 2;
mp["d"] = 2;
mp["f"] = 2;
mp["g"] = 2;
mp["h"] = 2;
mp["j"] = 2;
mp["k"] = 2;
mp["l"] = 2;
mp["z"] = 3;
mp["x"] = 3;
mp["c"] = 3;
mp["v"] = 3;
mp["b"] = 3;
mp["n"] = 3;
mp["m"] = 3;
// Traverse the array
for (const word of arr) {
// If current string is
// not an empty string
if (word.length !== 0) {
// Sets true / false if a string
// can be typed using keys of a
// single row or not
var flag = true;
// Stores row number of the first
// character of current string
var rowNum = mp[word[0].toLowerCase()];
// Stores length of word
var M = word.length;
// Traverse current string
for (var i = 1; i < M; i++) {
// If current character can't be
// typed using keys of rowNum only
if (mp[word[i].toLowerCase()] !== rowNum) {
// Update flag
flag = false;
break;
}
}
// If current string can be typed
// using keys from rowNum only
if (flag) {
// Print the string
document.write(word + " ");
}
}
}
}
// Driver Code
var words = ["Yeti", "Had", "GFG", "comment"];
findWordsSameRow(words);
</script>
Producción:
Yeti Had GFG
Complejidad de tiempo: O(N * M), donde N y M indican el número de strings y la longitud de la string más larga, respectivamente.
Espacio Auxiliar: O(26)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA