1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
private static class Holder {
private int pathSum;
}
public int pathSum(int[] nums) {
Map<Integer, Integer> dpToNumMap = new HashMap<>();
for (int num : nums) {
dpToNumMap.put(num / 10, num);
}
Holder holder = new Holder();
dfs(nums[0], 0, holder, dpToNumMap);
return holder.pathSum;
}
private void dfs(int num, int sum, Holder holder, Map<Integer, Integer> dpToNumMap) {
sum += num % 10;
int leftDp = (num / 100 + 1) * 10 + (num / 10 % 10) * 2 - 1;
int rightDp = leftDp + 1;
Integer leftNum = dpToNumMap.get(leftDp);
Integer rightNum = dpToNumMap.get(rightDp);
if (leftNum == null && rightNum == null) {
holder.pathSum += sum;
}
if (leftNum != null) {
dfs(leftNum, sum, holder, dpToNumMap);
}
if (rightNum != null) {
dfs(rightNum, sum, holder, dpToNumMap);
}
}
}
|