Weighted Prefix Search - GeeksforGeeks

Weighted Prefix Search - GeeksforGeeks

Given n strings and a weight associated with each string. The task is to find the maximum weight of string having the given prefix. Print “-1” if no string is present with given prefix.

Examples:

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.

    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);

       

    }

Method 1: (Brute Force)

Check all the string for given prefix, if string contains the prefix, compare its weight with maximum value so far.

Read full article from Weighted Prefix Search - GeeksforGeeks