Dada una serie de strings de alfabetos ingleses en minúsculas. La tarea es para cada letra [az] encontrar el número de strings que tienen estas letras.
Ejemplos:
Entrada: str = { «geeks», «for», «code» }
Salida: { 0 0 1 1 2 1 1 0 0 0 0 0 0 0 2 0 0 1 1 0 0 0 0 0 0 0 }
Explicación:
Para una letra, digamos ‘e’, está presente en { «geeks», «código»}, por lo tanto, su cuenta es 2.
De manera similar, se puede encontrar el resultado de otra letra.
Entrada: str = { «yo», «voluntad», «practica», «todos los días» }
Salida: 2 0 1 1 2 0 0 0 3 0 0 0 0 0 0 1 0 2 0 1 0 1 1 0 1 0
Explicación :
Para una letra, digamos ‘i’, está presente en { «i», «voluntad», «práctica»}, por lo tanto, su cuenta es 3.
De manera similar, se puede encontrar el resultado para otra letra.
Enfoque ingenuo:
- Cree un contador global para cada letra de tamaño 26, inicialícelo con 0.
- Ejecute un ciclo para cada una de las letras minúsculas del alfabeto inglés. Incrementa el contador de, por ejemplo, la letra ‘x’, si la letra actual se encuentra en la string actual.
- Repita esto para todo el alfabeto inglés en minúsculas.
Complejidad de tiempo: O(26*N), donde N es la suma de la longitud de todas las strings.
Enfoque eficiente:
- En lugar de ejecutar un ciclo para cada letra minúscula del alfabeto inglés y verificar si está presente en la string actual o no. En su lugar, podemos ejecutar un ciclo en cada string individualmente e incrementar el contador global para cualquier letra presente en esa string.
- Además, para evitar el recuento duplicado, creamos una array booleana visitada para marcar el encuentro de los personajes hasta el momento. Este enfoque reduce la complejidad a O(N).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find count of strings
// for each letter [a-z] in english alphabet
#include <bits/stdc++.h>
using namespace std;
// Function to find the countStrings
// for each letter [a-z]
void CountStrings(vector<string>& str)
{
int size = str.size();
// Initialize result as zero
vector<int> count(26, 0);
// Mark all letter as not visited
vector<bool> visited(26, false);
// Loop through each strings
for (int i = 0; i < size; ++i)
{
for (int j = 0; j < str[i].length(); ++j)
{
// Increment the global counter
// for current character of string
if (visited[str[i][j]] == false)
count[str[i][j] - 'a']++;
visited[str[i][j]] = true;
}
// Instead of re-initialising boolean
// vector every time we just reset
// all visited letter to false
for (int j = 0; j < str[i].length(); ++j)
{
visited[str[i][j]] = false;
}
}
// Print count for each letter
for (int i = 0; i < 26; ++i)
{
cout << count[i] << " ";
}
}
// Driver program
int main()
{
// Given array of strings
vector<string> str = {"i", "will",
"practice", "everyday"};
// Call the countStrings function
CountStrings(str);
return 0;
}
Java
// Java program to find count of Strings
// for each letter [a-z] in english alphabet
class GFG{
// Function to find the countStrings
// for each letter [a-z]
static void CountStrings(String []str)
{
int size = str.length;
// Initialize result as zero
int []count = new int[26];
// Mark all letter as not visited
boolean []visited = new boolean[26];
// Loop through each Strings
for (int i = 0; i < size; ++i)
{
for (int j = 0; j < str[i].length(); ++j)
{
// Increment the global counter
// for current character of String
if (visited[str[i].charAt(j) - 'a'] == false)
count[str[i].charAt(j) - 'a']++;
visited[str[i].charAt(j) - 'a'] = true;
}
// Instead of re-initialising boolean
// vector every time we just reset
// all visited letter to false
for (int j = 0; j < str[i].length(); ++j)
{
visited[str[i].charAt(j) - 'a'] = false;
}
}
// Print count for each letter
for (int i = 0; i < 26; ++i)
{
System.out.print(count[i] + " ");
}
}
// Driver program
public static void main(String[] args)
{
// Given array of Strings
String []str = {"i", "will",
"practice", "everyday"};
// Call the countStrings function
CountStrings(str);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program to find count of
# strings for each letter [a-z] in
# english alphabet
# Function to find the countStrings
# for each letter [a-z]
def CountStrings(s):
size = len(s)
# Initialize result as zero
count = [0] * 26
# Mark all letter as not visited
visited = [False] * 26
# Loop through each strings
for i in range(size):
for j in range(len(s[i])):
# Increment the global counter
# for current character of string
if visited[ord(s[i][j]) -
ord('a')] == False:
count[ord(s[i][j]) -
ord('a')] += 1
visited[ord(s[i][j]) -
ord('a')] = True
# Instead of re-initialising boolean
# vector every time we just reset
# all visited letter to false
for j in range(len(s[i])):
visited[ord(s[i][j]) -
ord('a')] = False
# Print count for each letter
for i in range(26):
print(count[i], end = ' ')
# Driver code
if __name__=='__main__':
# Given array of strings
s = [ "i", "will",
"practice", "everyday" ]
# Call the countStrings function
CountStrings(s)
# This code is contributed by rutvik_56
C#
// C# program to find count of Strings
// for each letter [a-z] in english alphabet
using System;
class GFG{
// Function to find the countStrings
// for each letter [a-z]
static void CountStrings(String []str)
{
int size = str.Length;
// Initialize result as zero
int []count = new int[26];
// Mark all letter as not visited
bool []visited = new bool[26];
// Loop through each Strings
for(int i = 0; i < size; ++i)
{
for(int j = 0; j < str[i].Length; ++j)
{
// Increment the global counter
// for current character of String
if (visited[str[i][j] - 'a'] == false)
count[str[i][j] - 'a']++;
visited[str[i][j] - 'a'] = true;
}
// Instead of re-initialising bool
// vector every time we just reset
// all visited letter to false
for(int j = 0; j < str[i].Length; ++j)
{
visited[str[i][j] - 'a'] = false;
}
}
// Print count for each letter
for(int i = 0; i < 26; ++i)
{
Console.Write(count[i] + " ");
}
}
// Driver code
public static void Main(String[] args)
{
// Given array of Strings
String []str = { "i", "will",
"practice", "everyday"};
// Call the countStrings function
CountStrings(str);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program to find count of strings
// for each letter [a-z] in english alphabet
// Function to find the countStrings
// for each letter [a-z]
function CountStrings(str)
{
let size = str.length;
// Initialize result as zero
let count = new Array(26).fill(0);
// Mark all letter as not visited
let visited = new Array(26).fill(false);
// Loop through each strings
for (let i = 0; i < size; ++i)
{
for (let j = 0; j < str[i].length; ++j)
{
// Increment the global counter
// for current character of string
if(visited[str[i].charCodeAt(j) - 97] == false)
count[str[i].charCodeAt(j) - 97]++;
visited[str[i].charCodeAt(j) - 97] = true;
}
// Instead of re-initialising boolean
// vector every time we just reset
// all visited letter to false
for (let j = 0; j < str[i].length; ++j)
{
visited[str[i].charCodeAt(j) - 97] = false;
}
}
// Print count for each letter
for (let i = 0; i < 26; ++i)
{
document.write(count[i]," ");
}
}
// Driver program
// Given array of strings
let str = ["i", "will","practice", "everyday"];
// Call the countStrings function
CountStrings(str);
// This code is contributed by shinjanpatra
</script>
Producción:
2 0 1 1 2 0 0 0 3 0 0 1 0 0 0 1 0 2 0 1 0 1 1 0 1 0
Complejidad de tiempo: O(N), donde N es la suma de la longitud de todas las strings.
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