Dada una array de strings arr[][ ] de tamaño N y una string S , la tarea es encontrar el número de strings de la array que tienen todos sus caracteres en la string S.
Ejemplos:
Entrada: arr[][] = {“ab”, “aab”, “abaaaa”, “bbd”}, S = “ab”
Salida: 3
Explicación: String “ab” tiene todos los caracteres que aparecen en la string S.
String “aab” tiene todos los caracteres que aparecen en la string S.
La string “abaaaa” tiene todos los caracteres que aparecen en la string S.Entrada: arr[] = {“geeks”, “for”, “geeks”}, S = “ds”
Salida: 0
Enfoque: La idea es usar Hashing para resolver el problema. Siga los pasos a continuación para resolver el problema:
- Inicialice un conjunto desordenado de caracteres, digamos válido , y una variable de contador, digamos cnt
- Inserte todos los caracteres de la string S en el conjunto válido .
- Recorra la array arr[] y realice los siguientes pasos:
- Itere sobre los caracteres de la string arr[i] y compruebe si todos los caracteres de la string arr[i] aparecen en la string S o no con la ayuda del conjunto válido .
- Si se encuentra que es cierto, entonces incremente cnt .
- Finalmente, imprima el resultado obtenido cnt
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 count the number of
// strings from an array having all
// characters appearing in the string S
int countStrings(string S, vector<string>& list)
{
// Initialize a set to store all
// distinct characters of string S
unordered_set<char> valid;
// Traverse over string S
for (auto x : S) {
// Insert characters
// into the Set
valid.insert(x);
}
// Stores the required count
int cnt = 0;
// Traverse the array
for (int i = 0; i < list.size(); i++) {
int j = 0;
// Traverse over string arr[i]
for (j = 0; j < list[i].size(); j++) {
// Check if character in arr[i][j]
// is present in the string S or not
if (valid.count(list[i][j]))
continue;
else
break;
}
// Increment the count if all the characters
// of arr[i] are present in the string S
if (j == list[i].size())
cnt++;
}
// Finally, print the count
return cnt;
}
// Driver code
int main()
{
vector<string> arr = { "ab", "aab",
"abaaaa", "bbd" };
string S = "ab";
cout << countStrings(S, arr) << endl;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
// Function to count the number of
// Strings from an array having all
// characters appearing in the String S
static int countStrings(String S, String []list)
{
// Initialize a set to store all
// distinct characters of String S
HashSet<Character> valid = new HashSet<Character>();
// Traverse over String S
for (char x : S.toCharArray())
{
// Insert characters
// into the Set
valid.add(x);
}
// Stores the required count
int cnt = 0;
// Traverse the array
for (int i = 0; i < list.length; i++)
{
int j = 0;
// Traverse over String arr[i]
for (j = 0; j < list[i].length(); j++)
{
// Check if character in arr[i][j]
// is present in the String S or not
if (valid.contains(list[i].charAt(j)))
continue;
else
break;
}
// Increment the count if all the characters
// of arr[i] are present in the String S
if (j == list[i].length())
cnt++;
}
// Finally, print the count
return cnt;
}
// Driver code
public static void main(String[] args)
{
String []arr = { "ab", "aab",
"abaaaa", "bbd" };
String S = "ab";
System.out.print(countStrings(S, arr) +"\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement
# the above approach
# Function to count the number of
# strings from an array having all
# characters appearing in the string S
def countStrings(S, list):
# Initialize a set to store all
# distinct characters of S
valid = {}
# Traverse over S
for x in S:
# Insert characters
# into the Set
valid[x] = 1
# Stores the required count
cnt = 0
# Traverse the array
for i in range(len(list)):
j = 0
# Traverse over arr[i]
while j < len(list[i]):
# Check if character in arr[i][j]
# is present in the S or not
if (list[i][j] in valid):
j += 1
continue
else:
break
j += 1
# Increment the count if all the characters
# of arr[i] are present in the S
if (j == len(list[i])):
cnt += 1
# Finally, print the count
return cnt
# Driver code
if __name__ == '__main__':
arr = ["ab", "aab", "abaaaa", "bbd"]
S,l = "ab",[]
print(countStrings(S, arr))
# This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to count the number of
// Strings from an array having all
// characters appearing in the String S
static int countStrings(String S, String []list)
{
// Initialize a set to store all
// distinct characters of String S
HashSet<char> valid = new HashSet<char>();
// Traverse over String S
foreach (char x in S.ToCharArray())
{
// Insert characters
// into the Set
valid.Add(x);
}
// Stores the required count
int cnt = 0;
// Traverse the array
for (int i = 0; i < list.Length; i++)
{
int j = 0;
// Traverse over String arr[i]
for (j = 0; j < list[i].Length; j++)
{
// Check if character in arr[i,j]
// is present in the String S or not
if (valid.Contains(list[i][j]))
continue;
else
break;
}
// Increment the count if all the characters
// of arr[i] are present in the String S
if (j == list[i].Length)
cnt++;
}
// Finally, print the count
return cnt;
}
// Driver code
public static void Main(String[] args)
{
String []arr = { "ab", "aab",
"abaaaa", "bbd" };
String S = "ab";
Console.Write(countStrings(S, arr) +"\n");
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to count the number of
// strings from an array having all
// characters appearing in the string S
function countStrings(S, list)
{
// Initialize a set to store all
// distinct characters of string S
let valid = new Set();
// Traverse over string S
for(let x of S)
{
// Insert characters
// into the Set
valid.add(x);
}
// Stores the required count
let cnt = 0;
// Traverse the array
for(let i = 0; i < list.length; i++)
{
let j = 0;
// Traverse over string arr[i]
for(j = 0; j < list[i].length; j++)
{
// Check if character in arr[i][j]
// is present in the string S or not
if (valid.has(list[i][j]))
continue;
else
break;
}
// Increment the count if all the characters
// of arr[i] are present in the string S
if (j == list[i].length)
cnt++;
}
// Finally, print the count
return cnt;
}
// Driver code
let arr = [ "ab", "aab",
"abaaaa", "bbd" ];
let S = "ab";
document.write(countStrings(S, arr) + "<br>");
// This code contributed by _saurabh_jaiswal
</script>
Producción:
3
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(N * M)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA