本文概述
给定ñ字符串以及与每个字符串关联的权重。任务是找到具有给定前缀的字符串的最大权重。如果没有带给定前缀的字符串, 则打印” -1″。
例子：
Input :
s1 = "geeks", w1 = 15
s2 = "geeksfor", w2 = 30
s3 = "srcmini", w3 = 45
prefix = geek
Output : 45
All the string contain the given prefix, but
maximum weight of string is 45 among all.方法1 ：(强力)
检查给定前缀的所有字符串, 如果字符串包含前缀, 则将其权重与到目前为止的最大值进行比较。
下面是上述想法的实现：
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" , "srcmini" };
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" , "srcmini" };
int weight[] = { 15 , 30 , 45 };
String prefix = "geek" ;
System.out.println(maxWeight(str, weight, n, prefix));
}
}
//This code is contributed by Sumit GhoshC#
//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" , "srcmini" };
int []weight = {15, 30, 45};
String prefix = "geek" ;
Console.WriteLine(maxWeight(str, weight, n, prefix));
}
}
//This code is contributed by vt_m.输出如下：
45方法2(有效)：
这个想法是创建和维护一个Trie。与其存储字符的普通Trie, 不如存储它的数字, 这是其前缀的最大值。当我们再次遇到前缀时, 使用现有和新的最大值来更新值。
现在, 搜索前缀以获取最大值, 从根开始搜索所有字符, 如果缺少一个字符则返回-1, 否则返回存储在根中的数字。
下面是上述想法的实现：
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" , "srcmini" };
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" , "srcmini" };
int weight[] = { 15 , 30 , 45 };
String prefix = "geek" ;
System.out.println(maxWeight(str, weight, n, prefix));
}
}
//This code is contributed by Sumit Ghosh45如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
来源：
https://www.srcmini02.com/69631.html
