Dadas n strings y un peso asociado a cada string. La tarea es encontrar el peso máximo de la string que tiene el prefijo dado. Imprima «-1» si no hay una string presente con el prefijo dado.
Ejemplos:
Input : s1 = "geeks", w1 = 15 s2 = "geeksfor", w2 = 30 s3 = "geeksforgeeks", w3 = 45 prefix = geek Output : 45 All the string contain the given prefix, but maximum weight of string is 45 among all.
Método 1: (Fuerza bruta)
Verifique toda la string para el prefijo dado, si la string contiene el prefijo, compare su peso con el valor máximo hasta el momento.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to find the maximum weight with given prefix.
// Brute Force based C++ program to find the
// string with maximum weight and given prefix.
#include<bits/stdc++.h>
#define MAX 1000
using namespace std;
// Return the maximum weight of string having
// given prefix.
int maxWeight(char str[MAX][MAX], int weight[],
int n, char prefix[])
{
int ans = -1;
bool check;
// Traversing all strings
for (int i = 0; i < n; i++)
{
check = true;
// Checking if string contain given prefix.
for (int j=0, k=0; j < strlen(str[i]) &&
k < strlen(prefix); j++, k++)
{
if (str[i][j] != prefix[k])
{
check = false;
break;
}
}
// If contain prefix then finding
// the maximum value.
if (check)
ans = max(ans, weight[i]);
}
return ans;
}
// Driven program
int main()
{
int n = 3;
char str[3][MAX] = { "geeks", "geeksfor", "geeksforgeeks" };
int weight[] = {15, 30, 45};
char prefix[] = "geek";
cout << maxWeight(str, weight, n, prefix) << endl;
return 0;
}
Java
// Java program to find the maximum
// weight with given prefix.
class GFG {
static final int MAX = 1000;
// Return the maximum weight of string having
// given prefix.
static int maxWeight(String str[], int weight[],
int n, String prefix)
{
int ans = -1;
boolean check;
// Traversing all strings
for (int i = 0; i < n; i++)
{
check = true;
// Checking if string contain given prefix.
for (int j=0, k=0; j < str[i].length() &&
k < prefix.length(); j++, k++)
{
if (str[i].charAt(j) != prefix.charAt(k))
{
check = false;
break;
}
}
// If contain prefix then finding
// the maximum value.
if (check)
ans = Math.max(ans, weight[i]);
}
return ans;
}
// Driven program
public static void main(String args[])
{
int n = 3;
String str[] = { "geeks", "geeksfor", "geeksforgeeks" };
int weight[] = {15, 30, 45};
String prefix = "geek";
System.out.println(maxWeight(str, weight, n, prefix));
}
}
//This code is contributed by Sumit Ghosh
C#
// C# program to find the maximum weight
// with given prefix.
using System;
class GFG
{
// Return the maximum weight of
// string having given prefix.
static int maxWeight(string []str, int []weight,
int n, string prefix)
{
int ans = -1;
bool check;
// Traversing all strings
for (int i = 0; i < n; i++)
{
check = true;
// Checking if string contain given prefix.
for (int j=0, k=0; j < str[i].Length &&
k < prefix.Length; j++, k++)
{
if (str[i][j] != prefix[k])
{
check = false;
break;
}
}
// If contain prefix then finding
// the maximum value.
if (check)
ans = Math.Max(ans, weight[i]);
}
return ans;
}
// Driver Code
public static void Main()
{
int n = 3;
String []str = {"geeks", "geeksfor",
"geeksforgeeks"};
int []weight = {15, 30, 45};
String prefix = "geek";
Console.WriteLine(maxWeight(str, weight,
n, prefix));
}
}
// This code is contributed by vt_m.
Javascript
<script>
// Javascript program to find the maximum weight with given prefix.
// Return the maximum weight of
// string having given prefix.
function maxWeight(str, weight, n, prefix)
{
let ans = -1;
let check;
// Traversing all strings
for (let i = 0; i < n; i++)
{
check = true;
// Checking if string contain given prefix.
for (let j=0, k=0; j < str[i].length &&
k < prefix.length; j++, k++)
{
if (str[i][j] != prefix[k])
{
check = false;
break;
}
}
// If contain prefix then finding
// the maximum value.
if (check)
ans = Math.max(ans, weight[i]);
}
return ans;
}
let n = 3;
let str = ["geeks", "geeksfor", "geeksforgeeks"];
let weight = [15, 30, 45];
let prefix = "geek";
document.write(maxWeight(str, weight,
n, prefix));
</script>
Producción:
45
Método 2 (eficiente):
La idea es crear y mantener un Trie. En lugar del Trie normal donde almacenamos el carácter, almacene un número con él, que es el valor máximo de su prefijo. Cuando volvamos a encontrar el prefijo, actualice el valor con el máximo de uno existente y uno nuevo.
Ahora, busque el prefijo para el valor máximo, recorra los caracteres comenzando desde la raíz, si falta uno de los caracteres, devuelva -1, de lo contrario, devuelva el número almacenado en la raíz.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to find the maximum weight
// with given prefix.
#include<bits/stdc++.h>
#define MAX 1000
using namespace std;
// Structure of a trie node
struct trieNode
{
// Pointer its children.
struct trieNode *children[26];
// To store weight of string.
int weight;
};
// Create and return a Trie node
struct trieNode* getNode()
{
struct trieNode *node = new trieNode;
node -> weight = INT_MIN;
for (int i = 0; i < 26; i++)
node -> children[i] = NULL;
}
// Inserting the node in the Trie.
struct trieNode* insert(char str[], int wt, int idx,
struct trieNode* root)
{
int cur = str[idx] - 'a';
if (!root -> children[cur])
root -> children[cur] = getNode();
// Assigning the maximum weight
root->children[cur]->weight =
max(root->children[cur]->weight, wt);
if (idx + 1 != strlen(str))
root -> children[cur] =
insert(str, wt, idx + 1, root -> children[cur]);
return root;
}
// Search and return the maximum weight.
int searchMaximum(char prefix[], struct trieNode *root)
{
int idx = 0, n = strlen(prefix), ans = -1;
// Searching the prefix in TRie.
while (idx < n)
{
int cur = prefix[idx] - 'a';
// If prefix not found return -1.
if (!root->children[cur])
return -1;
ans = root->children[cur]->weight;
root = root->children[cur];
++idx;
}
return ans;
}
// Return the maximum weight of string having given prefix.
int maxWeight(char str[MAX][MAX], int weight[], int n,
char prefix[])
{
struct trieNode* root = getNode();
// Inserting all string in the Trie.
for (int i = 0; i < n; i++)
root = insert(str[i], weight[i], 0, root);
return searchMaximum(prefix, root);
}
// Driven Program
int main()
{
int n = 3;
char str[3][MAX] = {"geeks", "geeksfor", "geeksforgeeks"};
int weight[] = {15, 30, 45};
char prefix[] = "geek";
cout << maxWeight(str, weight, n, prefix) << endl;
return 0;
}
Java
// Java program to find the maximum weight
// with given prefix.
public class GFG{
static final int MAX = 1000;
// Structure of a trie node
static class TrieNode
{
// children
TrieNode[] children = new TrieNode[26];
// To store weight of string.
int weight;
// constructor
public TrieNode() {
weight = Integer.MIN_VALUE;
for (int i = 0; i < 26; i++)
children[i] = null;
}
}
//static TrieNode root;
// Inserting the node in the Trie.
static TrieNode insert(String str, int wt, int idx, TrieNode root)
{
int cur = str.charAt(idx) - 'a';
if (root.children[cur] == null)
root.children[cur] = new TrieNode();
// Assigning the maximum weight
root.children[cur].weight =
Math.max(root.children[cur].weight, wt);
if (idx + 1 != str.length())
root.children[cur] =
insert(str, wt, idx + 1, root.children[cur]);
return root;
}
// Search and return the maximum weight.
static int searchMaximum(String prefix, TrieNode root)
{
int idx = 0, ans = -1;
int n = prefix.length();
// Searching the prefix in TRie.
while (idx < n)
{
int cur = prefix.charAt(idx) - 'a';
// If prefix not found return -1.
if (root.children[cur] == null)
return -1;
ans = root.children[cur].weight;
root = root.children[cur];
++idx;
}
return ans;
}
// Return the maximum weight of string having given prefix.
static int maxWeight(String str[], int weight[], int n,
String prefix)
{
TrieNode root = new TrieNode();
// Inserting all string in the Trie.
for (int i = 0; i < n; i++)
root = insert(str[i], weight[i], 0, root);
return searchMaximum(prefix, root);
}
// Driven Program
public static void main(String args[])
{
int n = 3;
String str[] = { "geeks", "geeksfor", "geeksforgeeks" };
int weight[] = {15, 30, 45};
String prefix = "geek";
System.out.println(maxWeight(str, weight, n, prefix));
}
}
//This code is contributed by Sumit Ghosh
45
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuido@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA