Java and C# solutions using Trie with Explanation


  • 0

    The idea is to create a Trie and update it when an Insert method is called. Trie nodes are called MapSumNode.
    For each of the characters in the given string, once adding to trie, we not only store the character, but also store the current value that is assigned to current string. So all the characters of the string will have the same value.

    For example:
    Insert("apple",5) --> ('a',5) ('a',5) ('p',5) ('p',5) ('l',5) ('e',5)
    Insert("app",2) --> ('a',7) ('p',7) ('p',7)

    We also keep track of the strings using a HashMap (Dictionary in C#). If the current string has already been seen, we find the difference between new and old value (newValue) and update the characters with the new value by calling Insert method. For example if "apple" used to have value of 5 and now should be updated to 2, we set the newValue to 2-5=-3 and update the corresponding MapSumNodes by subtracting 3 from their previous value.

    Finding the result by calling Sum method is now so easy. We just traverse over the trie. If the given prefix doesn't exist we just return 0 (I found it out by submitting my code few times, it should have been given with problem restrictions), otherwise return the value (currSum) assigned to the last MapSumNode which has the last character of prefix.

    Java:

    public class MapSum
    {
        MapSumNode root;
        HashMap<String, Integer> latestValue;
    
        public MapSum()
        {
            root = new MapSumNode();
            latestValue = new HashMap<String, Integer>();
        }
    
        public void insert(String key, int val)
        {
            Integer newValue = val;
            if (latestValue.containsKey(key))
            {
                newValue = val - latestValue.get(key); //diff
            }
            latestValue.put(key, val);
            root.Insert(key, newValue);
        }
    
        public int sum(String prefix)
        {
            return root.SumOfPrefix(prefix);
        }
    
        class MapSumNode
        {
            public HashMap<Character, MapSumNode> Children;
            public int currSum;
            public Character c;
    
            public MapSumNode()
            {
                Children = new HashMap<Character, MapSumNode>();
            }
    
            public MapSumNode(char ch)
            {
                Children = new HashMap<Character, MapSumNode>();
                currSum = 0;
                c = ch;
            }
    
            public void Insert(String s, int value)
            {
                HashMap<Character, MapSumNode> currChildren = Children;
    
                for (int i = 0; i < s.length(); i++)
                {
                    MapSumNode temp;
    
                    if (currChildren.containsKey(s.charAt(i)))
                    {
                        temp = currChildren.get(s.charAt(i));
                    }
                    else
                    {
                        temp = new MapSumNode(s.charAt(i));
                        currChildren.put(s.charAt(i), temp);
                    }
                    temp.currSum += value;
                    currChildren = temp.Children;
                }
            }
    
            public int SumOfPrefix(String prefix)
            {
                HashMap<Character, MapSumNode> currChildren = Children;
                int result = 0;
    
                for (int i = 0; i < prefix.length(); i++)
                {
                    if (!currChildren.containsKey(prefix.charAt(i))) return 0;
    
                    MapSumNode currNode = currChildren.get(prefix.charAt(i));
                    result = currNode.currSum;
                    currChildren = currNode.Children;
                }
    
                return result;
            }
        }
    }
    
    

    C#:

        public class MapSum
        {
            MapSumNode root;
            Dictionary<string, int> latestValue;
            /** Initialize your data structure here. */
            public MapSum()
            {
                root = new MapSumNode();
                latestValue = new Dictionary<string, int>();
            }
    
            public void Insert(string key, int val)
            {
                int newValue = val;
                if (latestValue.ContainsKey(key))
                {
                    newValue = val - latestValue[key];//diff
                    latestValue[key] = val;
                }
                else
                    latestValue.Add(key, val);
                root.Insert(key, newValue);
            }
    
            public int Sum(string prefix)
            {
                return root.SumOfPrefix(prefix);
            }
        }
        public class MapSumNode
        {
            public Dictionary<char, MapSumNode> Children;
            public int currSum;
            public char c;
            public MapSumNode()
            {
                Children = new Dictionary<char, MapSumNode>();
            }
            public MapSumNode(char ch)
            {
                Children = new Dictionary<char, MapSumNode>();
                currSum = 0;
                c = ch;
            }
    
            public void Insert(string s, int value)
            {
                Dictionary<char, MapSumNode> currChildren = Children;
    
                for (int i = 0; i < s.Length; i++)
                {
                    MapSumNode temp;
    
                    if(currChildren.ContainsKey(s[i]))
                    {
                        temp= currChildren[s[i]];
                    }
                    else
                    {
                        temp = new MapSumNode(s[i]);
                        currChildren.Add(s[i], temp);
                    }
                    temp.currSum += value;
                    currChildren = temp.Children;
                }
            }
    
            public int SumOfPrefix(string prefix)
            {
                Dictionary<char, MapSumNode> currChildren = Children;
                int result = 0;
    
                for (int i = 0; i < prefix.Length; i++)
                {
                    if(!currChildren.ContainsKey(prefix[i]))return 0;
    
                    MapSumNode currNode = currChildren[prefix[i]];
                    result = currNode.currSum;
                    currChildren = currNode.Children;
                }
    
                return result;
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.