个性化阅读
专注于IT技术分析

算法设计:加权前缀搜索介绍和实现

点击下载

本文概述

给定ñ字符串以及与每个字符串关联的权重。任务是找到具有给定前缀的字符串的最大权重。如果没有带给定前缀的字符串, 则打印” -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 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" , "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 Ghosh
45

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

赞(2)
未经允许不得转载:srcmini » 算法设计:加权前缀搜索介绍和实现

评论 抢沙发

评论前必须登录!