Dada una array de strings arr[] y dadas algunas consultas donde cada consulta consta de una string str y un entero k . La tarea es encontrar el conteo de strings en arr[] cuyo prefijo de longitud k coincida con el prefijo de longitud k de str .
Ejemplos:
Entrada: arr[] = {“abba”, “abbb”, “abbc”, “abbd”, “abaa”, “abca”}, str = “abbg”, k = 3
Salida: 4
“abba”, “abbb ”, “abbc” y “abbd” son las strings coincidentes.
Entrada: arr[] = {“geeks”, “geeksforgeeks”, “forgeeks”}, str = “geeks”, k = 2
Salida: 2
Requisito previo: Trie | (Insertar y buscar)
Enfoque: formaremos un trie e insertaremos todas las strings en el trie y crearemos otra variable (frecuencia) para cada Node que almacenará la frecuencia del prefijo de las strings dadas. Ahora, para obtener el recuento de strings cuyo prefijo coincida con la string dada a una longitud k dada, tendremos que atravesar el trie hasta la longitud k desde la raíz, la frecuencia del Node dará el recuento de tales strings.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Trie node (considering only lowercase alphabets)
struct Node {
Node* arr[26];
int freq;
};
// Function to insert a node in the trie
Node* insert(string s, Node* root)
{
int in;
Node* cur = root;
for (int i = 0; i < s.length(); i++) {
in = s[i] - 'a';
// If there is no node created then create one
if (cur->arr[in] == NULL)
cur->arr[in] = new Node();
// Increase the frequency of the node
cur->arr[in]->freq++;
// Move to the next node
cur = cur->arr[in];
}
// Return the updated root
return root;
}
// Function to return the count of strings
// whose prefix of length k matches with the
// k length prefix of the given string
int find(string s, int k, Node* root)
{
int in, count = 0;
Node* cur = root;
// Traverse the string
for (int i = 0; i < s.length(); i++) {
in = s[i] - 'a';
// If there is no node then return 0
if (cur->arr[in] == NULL)
return 0;
// Else traverse to the required node
cur = cur->arr[in];
count++;
// Return the required count
if (count == k)
return cur->freq;
}
return 0;
}
// Driver code
int main()
{
string arr[] = { "abba", "abbb", "abbc", "abbd", "abaa", "abca" };
int n = sizeof(arr) / sizeof(string);
Node* root = new Node();
// Insert the strings in the trie
for (int i = 0; i < n; i++)
root = insert(arr[i], root);
// Query 1
cout << find("abbg", 3, root) << endl;
// Query 2
cout << find("abg", 2, root) << endl;
// Query 3
cout << find("xyz", 2, root) << endl;
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Trie node (considering only lowercase alphabets)
static class Node
{
Node[] arr = new Node[26];
int freq;
};
// Function to insert a node in the trie
static Node insert(String s, Node root)
{
int in;
Node cur = root;
for (int i = 0; i < s.length(); i++)
{
in = s.charAt(i) - 'a';
// If there is no node created then create one
if (cur.arr[in] == null)
cur.arr[in] = new Node();
// Increase the frequency of the node
cur.arr[in].freq++;
// Move to the next node
cur = cur.arr[in];
}
// Return the updated root
return root;
}
// Function to return the count of Strings
// whose prefix of length k matches with the
// k length prefix of the given String
static int find(String s, int k, Node root)
{
int in, count = 0;
Node cur = root;
// Traverse the String
for (int i = 0; i < s.length(); i++)
{
in = s.charAt(i) - 'a';
// If there is no node then return 0
if (cur.arr[in] == null)
return 0;
// Else traverse to the required node
cur = cur.arr[in];
count++;
// Return the required count
if (count == k)
return cur.freq;
}
return 0;
}
// Driver code
public static void main(String[] args)
{
String arr[] = { "abba", "abbb", "abbc",
"abbd", "abaa", "abca" };
int n = arr.length;
Node root = new Node();
// Insert the Strings in the trie
for (int i = 0; i < n; i++)
root = insert(arr[i], root);
// Query 1
System.out.print(find("abbg", 3, root) + "\n");
// Query 2
System.out.print(find("abg", 2, root) + "\n");
// Query 3
System.out.print(find("xyz", 2, root) + "\n");
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the approach
# Trie node (considering only lowercase alphabets)
class Node :
def __init__(self):
self.arr = [None]*26
self.freq = 0
class Trie:
# Trie data structure class
def __init__(self):
self.root = self.getNode()
def getNode(self):
# Returns new trie node (initialized to NULLs)
return Node()
# Function to insert a node in the trie
def insert(self, s):
_in = 0
cur = self.root
for i in range(len(s)):
_in = ord(s[i]) - ord('a')
# If there is no node created then create one
if not cur.arr[_in]:
cur.arr[_in] = self.getNode()
# Increase the frequency of the node
cur.arr[_in].freq += 1
# Move to the next node
cur = cur.arr[_in]
# Function to return the count of strings
# whose prefix of length k matches with the
# k length prefix of the given string
def find(self, s, k):
_in = 0
count = 0
cur = self.root
# Traverse the string
for i in range(len(s)):
_in = ord(s[i]) - ord('a')
# If there is no node then return 0
if cur.arr[_in] == None:
return 0
# Else traverse to the required node
cur = cur.arr[_in]
count += 1
# Return the required count
if count == k:
return cur.freq
return 0
# Driver code
def main():
arr = [ "abba", "abbb", "abbc", "abbd", "abaa", "abca" ]
n = len(arr)
root = Trie();
# Insert the strings in the trie
for i in range(n):
root.insert(arr[i])
# Query 1
print(root.find("abbg", 3))
# Query 2
print(root.find("abg", 2))
# Query 3
print(root.find("xyz", 2))
if __name__ == '__main__':
main()
# This code is contributed by divyamohan123
C#
// C# implementation of the approach
using System;
class GFG
{
// Trie node (considering only lowercase alphabets)
public class Node
{
public Node[] arr = new Node[26];
public int freq;
};
// Function to insert a node in the trie
static Node insert(String s, Node root)
{
int iN;
Node cur = root;
for (int i = 0; i < s.Length; i++)
{
iN = s[i] - 'a';
// If there is no node created then create one
if (cur.arr[iN] == null)
cur.arr[iN] = new Node();
// Increase the frequency of the node
cur.arr[iN].freq++;
// Move to the next node
cur = cur.arr[iN];
}
// Return the updated root
return root;
}
// Function to return the count of Strings
// whose prefix of length k matches with the
// k length prefix of the given String
static int find(String s, int k, Node root)
{
int iN, count = 0;
Node cur = root;
// Traverse the String
for (int i = 0; i < s.Length; i++)
{
iN = s[i] - 'a';
// If there is no node then return 0
if (cur.arr[iN] == null)
return 0;
// Else traverse to the required node
cur = cur.arr[iN];
count++;
// Return the required count
if (count == k)
return cur.freq;
}
return 0;
}
// Driver code
public static void Main(String[] args)
{
String []arr = { "abba", "abbb", "abbc",
"abbd", "abaa", "abca" };
int n = arr.Length;
Node root = new Node();
// Insert the Strings in the trie
for (int i = 0; i < n; i++)
root = insert(arr[i], root);
// Query 1
Console.Write(find("abbg", 3, root) + "\n");
// Query 2
Console.Write(find("abg", 2, root) + "\n");
// Query 3
Console.Write(find("xyz", 2, root) + "\n");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the approach
// Trie node (considering only lowercase alphabets)
class Node
{
constructor()
{
this.arr=new Array(26);
this.freq=0;
}
}
// Function to insert a node in the trie
function insert(s,root)
{
let In;
let cur = root;
for (let i = 0; i < s.length; i++)
{
In = s[i].charCodeAt(0) - 'a'.charCodeAt(0);
// If there is no node created then create one
if (cur.arr[In] == null)
cur.arr[In] = new Node();
// Increase the frequency of the node
cur.arr[In].freq++;
// Move to the next node
cur = cur.arr[In];
}
// Return the updated root
return root;
}
// Function to return the count of Strings
// whose prefix of length k matches with the
// k length prefix of the given String
function find(s,k,root)
{
let In, count = 0;
let cur = root;
// Traverse the String
for (let i = 0; i < s.length; i++)
{
In = s[i].charCodeAt(0) - 'a'.charCodeAt(0);
// If there is no node then return 0
if (cur.arr[In] == null)
return 0;
// Else traverse to the required node
cur = cur.arr[In];
count++;
// Return the required count
if (count == k)
return cur.freq;
}
return 0;
}
// Driver code
let arr=["abba", "abbb", "abbc",
"abbd", "abaa", "abca"];
let n = arr.length;
let root = new Node();
// Insert the Strings in the trie
for (let i = 0; i < n; i++)
root = insert(arr[i], root);
// Query 1
document.write(find("abbg", 3, root) + "<br>");
// Query 2
document.write(find("abg", 2, root) + "<br>");
// Query 3
document.write(find("xyz", 2, root) + "<br>");
// This code is contributed by rag2127
</script>
Producción
4 6 0
Aproximación sin usar Trie:
La idea es usar una substring de longitud k. Dado que estamos tratando con prefijos, debemos considerar la substring de longitud k a partir del índice 0. Esta substring siempre será el prefijo de la string. Almacene la substring de longitud k de str del índice 0 en una string a. Ejecute un ciclo para cada palabra en la array de strings y para cada palabra que tenga una longitud mayor que k, tome la substring de longitud k comenzando desde el índice 0. Ahora verifique la igualdad de las dos substrings a y b. Si los dos son iguales, aumente la cuenta. Finalmente, después de salir del bucle, devuelve el conteo.
C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int klengthpref(string arr[], int n, int k, string str)
{
string a = str.substr(
0, k); // storing k-length substring of str
int count
= 0; // counter to count the matching condition
// looping through each word of arr
for (int i = 0; i < n; i++) {
if (arr[i].length()
< k) // if the length of string from arr is
// less than k
continue; // then there is no point in
// finding the substring so we
// skip
string b = arr[i].substr(
0, k); // storing k-length substring of each
// string from arr
if (a == b) // checking equality of the two
// substring a and b
count++; // if condition matches increase
// the counter
}
return count; // finally return the count
}
};
int main()
{
string arr[] = { "abba", "abbb", "abbc",
"abbd", "abaa", "abca" };
string str = "abbg";
int n = sizeof(arr) / sizeof(string), k = 3;
Solution ob;
cout << ob.klengthpref(arr, n, k, str);
return 0;
}
Java
class GFG {
public static void main(String args[])
{
String[] arr = { "abba", "abbb", "abbc",
"abbd", "abaa", "abca" };
String str = "abbg";
int n = arr.length, k = 3;
Solution obj = new Solution();
int ans = obj.klengthpref(arr, n, k, str);
System.out.println(ans);
}
}
class Solution {
public int klengthpref(String[] arr, int n, int k,
String str)
{
String a = str.substring(
0, k); // storing k-length substring of str
int count
= 0; // counter to count the matching condition
// looping through each word of arr
for (int i = 0; i < n; i++) {
if (arr[i].length()
< k) // if the length of string from arr is
// less than k
continue; // then there is no point in
// finding the substring so we
// skip
String b = arr[i].substring(
0, k); // storing k-length substring of each
// string from arr
if (a.equals(b)) // checking equality of the two
// substring a and b
count++; // if condition matches increase
// the counter
}
return count; // finally return the count
}
}
Python3
class Solution: def klengthpref(self, arr, n, k, s): a = s[:k] # storing k-length substring of str count = 0 # counter to count the matching condition # looping through each word of arr for i in range(n): if(len(arr[i]) < k): # if the length of string from arr is less than k continue # then there is no point in finding the substring so we skip t = arr[i] b = t[:k] # storing k-length substring of each string from arr if(a == b): # checking equality of the two substring a and b count += 1 # if condition matches increase the counter by 1 return count # finally return the count arr = ["abba", "abbb", "abbc", "abbd", "abaa", "abca"] str = "abbg" n = len(arr) k = 3 obj = Solution() print(obj.klengthpref(arr, n, k, str))
Producción
4
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA