Poison

666. Path Sum IV

发表于 
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);
        }
    }
}
Reference

666. Path Sum IV