MapSumPairs [source code]
public class MapSumPairs {
static
/******************************************************************************/
class MapSum {
TrieNode root;
public MapSum() {
root = new TrieNode ();
}
public void insert(String key, int val) {
if (key.length () == 0)
return;
char[] chs = key.toCharArray ();
TrieNode cur = root;
for (char c : chs) {
if (cur.links[c - 'a'] == null)
cur.links[c - 'a'] = new TrieNode ();
cur = cur.links[c - 'a'];
}
cur.val = val;
}
public int sum(String prefix) {
if (prefix.length () == 0)
return 0;
char[] chs = prefix.toCharArray ();
int res = 0;
TrieNode cur = root;
for (char c : chs) {
if (cur.links[c - 'a'] == null)
return res;
cur = cur.links[c - 'a'];
}
// assert cur.val != null; // this is wrong, you can't assert this
return res + dfs (cur);
}
int dfs (TrieNode node) {
if (node == null)
return 0;
int res = 0;
if (node.val != null)
res += node.val;
for (TrieNode child : node.links)
res += dfs (child);
return res;
}
static class TrieNode {
Integer val = null;
TrieNode[] links = new TrieNode[26];
}
}
/******************************************************************************/
public static void main(String[] args) {
MapSumPairs.MapSum tester = new MapSumPairs.MapSum();
}
}
题目意思本身不是很难理解, 就是一个trie题; 细节上面自己注意一下就行了;
感觉我对trie问题有点熟悉了, 最后居然直接秒杀了这个题目, 不过速度不怎么样: 128ms (21%), 但是可以接受了;
editorial
第一个, 笨办法:
class MapSum {
HashMap<String, Integer> map;
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;
}
}
Approach #2: Prefix Hashmap [Accepted]
Intuition and Algorithm
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.)
class MapSum {
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);
}
}
这个做法其实也没有什么特别的地方, 就是加了一个memo, 不过这个memo好像不是那么trivial: 因为对于一个prefix, 以及其所对应的所有的string, 你这个时候的差值的计算要考虑这个string之前的val, 所以他这里insert第一行的delta的计算要考虑原来的map[key];
Approach #3: Trie [Accepted]
Intuition and Algorithm
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].
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;
}
虽然同样是trie的算法, 但是可以看到他这里的算法跟我的做法有两个不同:
- 首先就是他的links还是用的一个Map, 而不是一个array, 这个是awice的一贯做法了; 当然了, 不是说这个不好, 毕竟Map的普适性更强; 但是这里看到另外一个好处:
cur.children.putIfAbsent(c, new TrieNode());: 看这里, 利用Map的这个putIfAbsent操作, 很多写法上就更加方便; 另外, 这里不要用computeIfAbsent了, 这个putIfAbsent函数我其实还是第一次见到用, 以后就可以用了; - 他的trie的node里面, 存的不是单个的val, 而是一个sum, 这样对于
sum的service就更加的快; 这个也是更加贴切题目意图的一个改动; 当然了, 对应于这样的一个设计改动, 最后insert的操作就相应的要增加; 这里每一次insert的时候, 就要跟上面第二种做法那样, 更新一个delta; 这个也是为什么他要维护map;
总体来说他这个做法肯定是比我的要好的, 因为我的每一次sum都要专门做一次DFS, 这个速度就很坑爹了;
discussion最优解, 其实跟我的是一样的:
@shawngao said in Java solution, Trie:
class MapSum {
class TrieNode {
Map<Character, TrieNode> children;
boolean isWord;
int value;
public TrieNode() {
children = new HashMap<Character, TrieNode>();
isWord = false;
value = 0;
}
}
TrieNode root;
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;
}
}
另外我是用Integer的Null来判断当前node是否有值, 而他是专门加了一个boolean来维护; 这个技巧也要相对的熟悉; 事实上, 我太过于依赖special value带来的conciseness, 导致我在写Pintos的时候, 对于简单的flag + value这样的互相维护组合技巧非常的不熟悉, 这个也是我一个长期需要克服的短板;
这个是discussion另外一个有意思的帖子:
@wavy said in 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 ofs += 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/PjymymghBut 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
O(1)
Time Complexity for insert isO(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);
}
这个就是editorial2的解法, 我当时看那个解法的时候, 还认为在insert里面s+=c这个操作很聪明, 但是实际上完全不是, 这里看到, 就算是你换成了char的操作, 最后还是没有避免string操作带来的cost;
注意, 这个cost是没有办法用StringBuilder规避的:
@wavy said in Simple Java HashMap Solution - O(1) sum, and O(len(key)) insert:
@kangbin2356 No, because I still have to create a string out of it, so if I use a string builder, I still have to do stringbuilder.toString() in every loop.
这题因为已经看到很多种优秀解法了, 所以discussion就没有继续向后看了; submission的排名很扯淡, 第一名居然是editorial1那样的暴力解法, 不管了; 这题如果最后想让你做出来的是那个暴力解法, 那么肯定不可能希望被标记为medium题的;
Problem Description
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
Difficulty:Medium
Total Accepted:8.5K
Total Submissions:16.2K
Contributor:今が最高
Companies
akuna capital
Related Topics
trie
/**
- Your MapSum object will be instantiated and called as such:
- MapSum obj = new MapSum();
- obj.insert(key,val);
- int param_2 = obj.sum(prefix);
*/