https://leetcode.com/problems/map-sum-pairs/solution/
Since we are dealing with prefixes, a Trie (prefix tree) is a natural data structure to approach this problem. For every node of the trie corresponding to some prefix, we will remember the desired answer (score) and store it at this node. As in Approach #2, this involves modifying each node by
https://leetcode.com/problems/map-sum-pairs/discuss/107513/Java-solution-Trie
X. Prefix Hashmap
public MapSum() {
map = new HashMap<>();
}
public void insert(String key, int val) {
map.put(key, val);
}
public int sum(String prefix) {
int ans = 0;
for (String key: map.keySet()) {
if (key.startsWith(prefix)) {
ans += map.get(key);
}
}
return ans;
}
https://leetcode.com/problems/map-sum-pairs/discuss/107515/Simple-Java-HashMap-Solution-O(1)-sum-and-O(len(key))-insert
Implement a MapSum class with
insert, and sum methods.
For the method
insert, you'll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.
For the method
sum, you'll be given a string representing the prefix, and you need to return the sum of all the pairs' value whose key starts with the prefix.
Example 1:
Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5
Since we are dealing with prefixes, a Trie (prefix tree) is a natural data structure to approach this problem. For every node of the trie corresponding to some prefix, we will remember the desired answer (score) and store it at this node. As in Approach #2, this involves modifying each node by
delta = val - map[key]- Time Complexity: Every insert operation is , where is the length of the key. Every sum operation is .
- Space Complexity: The space used is linear in the size of the total input.
class MapSum {
HashMap<String, Integer> map;
TrieNode root;
public MapSum() {
map = new HashMap();
root = new TrieNode();
}
public void insert(String key, int val) {
int delta = val - map.getOrDefault(key, 0);
map.put(key, val);
TrieNode cur = root;
cur.score += delta;
for (char c: key.toCharArray()) {
cur.children.putIfAbsent(c, new TrieNode());
cur = cur.children.get(c);
cur.score += delta;
}
}
public int sum(String prefix) {
TrieNode cur = root;
for (char c: prefix.toCharArray()) {
cur = cur.children.get(c);
if (cur == null) return 0;
}
return cur.score;
}
}
class TrieNode {
Map<Character, TrieNode> children = new HashMap();
int score;
}
private Trie trie = new Trie();
public void insert(String key, int val) {
trie.insert(key, val);
}
public int sum(String prefix) {
Optional<TrieNode> node = trie.prefixSearch(prefix);
if (!node.isPresent())
return 0;
return node.get().count;
}
// when use char
// -'0' -'a'
private static class Trie {
private TrieNode root = new TrieNode();
public void insert(String key, int val) {
TrieNode cur = root;
List<TrieNode> parents = new ArrayList<>();
boolean added = false;
for (char ch : key.toCharArray()) {
TrieNode child = cur.children[getIndex(ch)];
if (child == null) {
added = true;
child = new TrieNode();
cur.children[getIndex(ch)] = child;
}
parents.add(child);
// child.ch = ch;
// child.count += val;
cur = child;
}
int diff = val;
if (!added && cur.isEnd) {
// add same
diff = val - cur.count;
}
for (TrieNode node : parents) {
node.count += diff;
}
cur.isEnd = true;
// can't use mutable variable in stream
// parents.stream().forEach(node -> node.count += diff);
}
public Optional<TrieNode> prefixSearch(String prefix) {
TrieNode cur = root;
for (char ch : prefix.toCharArray()) {
TrieNode child = cur.children[getIndex(ch)];
cur = child;
if (cur == null) {
return Optional.empty();
}
}
return Optional.ofNullable(cur);
}
private int getIndex(char ch) {
return ch - 'a';
}
}
private static class TrieNode {
// private char ch;// do we need it
private boolean isEnd;
private int count;
public TrieNode[] children = new TrieNode[26];
}
class TrieNode {
Map<Character, TrieNode> children;
boolean isWord;
int value;
public TrieNode() {
children = new HashMap<Character, TrieNode>();
isWord = false;
value = 0;
}
}
TrieNode root;
/** Initialize your data structure here. */
public MapSum() {
root = new TrieNode();
}
public void insert(String key, int val) {
TrieNode curr = root;
for (char c : key.toCharArray()) {
TrieNode next = curr.children.get(c);
if (next == null) {
next = new TrieNode();
curr.children.put(c, next);
}
curr = next;
}
curr.isWord = true;
curr.value = val;
}
public int sum(String prefix) {
TrieNode curr = root;
for (char c : prefix.toCharArray()) {
TrieNode next = curr.children.get(c);
if (next == null) {
return 0;
}
curr = next;
}
return dfs(curr);
}
private int dfs(TrieNode root) {
int sum = 0;
for (char c : root.children.keySet()) {
sum += dfs(root.children.get(c));
}
return sum + root.value;
}X. Prefix Hashmap
We can remember the answer for all possible prefixes in a HashMap
score. When we get a new (key, val)pair, we update every prefix of key appropriately: each prefix will be changed by delta = val - map[key], where map is the previous associated value of key (zero if undefined.)- Time Complexity: Every insert operation is , where is the length of the key, as strings are made of an average length of . Every sum operation is .
- Space Complexity: The space used by
mapandscoreis linear in the size of all inputkeyandvalvalues combined.
Map<String, Integer> map;
Map<String, Integer> score;
public MapSum() {
map = new HashMap();
score = new HashMap();
}
public void insert(String key, int val) {
int delta = val - map.getOrDefault(key, 0);
map.put(key, val);
String prefix = "";
for (char c: key.toCharArray()) {
prefix += c;
score.put(prefix, score.getOrDefault(prefix, 0) + delta);
}
}
public int sum(String prefix) {
return score.getOrDefault(prefix, 0);
}
- Time Complexity: Every insert operation is . Every sum operation is where is the number of items in the map, and is the length of the input prefix.
- Space Complexity: The space used by
mapis linear in the size of all inputkeyandvalvalues combined.
public MapSum() {
map = new HashMap<>();
}
public void insert(String key, int val) {
map.put(key, val);
}
public int sum(String prefix) {
int ans = 0;
for (String key: map.keySet()) {
if (key.startsWith(prefix)) {
ans += map.get(key);
}
}
return ans;
}
https://leetcode.com/problems/map-sum-pairs/discuss/107515/Simple-Java-HashMap-Solution-O(1)-sum-and-O(len(key))-insert
UPDATE : Okay, let me tell you that even though solution look so concise, why you should NOT do this.
It's because of
It's because of
s += c. This operation is not O(1), it's O(String::length), which makes for loop to be k^2. And this will break when string is long. Try it yourself as learning with this input for insert - https://pastebin.com/Pjymymgh
But if the constraint is that the string are small, like dictionary words or people names, then it should be good.
The key idea is to keep two hash maps, one with just original strings. The other with all prefixes.
When a duplicate insert is found, then update all it's prefixes with the difference of previous value of the same key(take it from original map)
Time Complexity for sum is
Time Complexity for insert is
O(1)Time Complexity for insert is
O(len(key))O(len(key) ^ 2)Map<String, Integer> map;
Map<String, Integer> original;
public MapSum() {
map = new HashMap<>();
original = new HashMap<>();
}
public void insert(String key, int val) {
val -= original.getOrDefault(key, 0); // calculate the diff to be added to prefixes
String s = "";
for(char c : key.toCharArray()) {
s += c; // creating all prefixes
map.put(s, map.getOrDefault(s, 0) + val); //update/insert all prefixes with new value
}
original.put(key, original.getOrDefault(key, 0) + val);
}
public int sum(String prefix) {
return map.getOrDefault(prefix, 0);
} HashMap<String, Integer> map;
/** Initialize your data structure here. */
public MapSum() {
map = new HashMap<>();
}
public void insert(String key, int val) {
map.put(key, val);
}
public int sum(String prefix) {
int sum = 0;
for (Map.Entry<String, Integer> entry: map.entrySet()) {
if (entry.getKey().startsWith(prefix)) {
sum += entry.getValue();
}
}
return sum;
}