鉴于 N 字符串和与每条字符串关联的权重。任务是找到具有给定前缀的字符串的最大重量。如果没有带给定前缀的字符串，则打印“-1”。 例如：
null
Input : s1 = "geeks", w1 = 15s2 = "geeksfor", w2 = 30s3 = "geeksforgeeks", w3 = 45prefix = geekOutput : 45All the string contain the given prefix, butmaximum 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" , "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> |
输出：
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" , "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
本文由 阿努伊·乔汉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
