390. Hierarchical String Value Aggregation

Fulltime8/20/2025
Google

Problem Description

You are given a list of hierarchical string entries, each with an associated integer value. Each entry represents a path in a hierarchy, similar to a file system path or a domain name. The goal is to compute the aggregated value for each leaf node in the hierarchy. The aggregation rule is that each entry's value contributes to itself and all of its ancestors. Specifically, you are given a list of strings and corresponding integer values. Each string represents a path, where parts of the path are separated by dots (`.`). For example, `"a.b.c"` represents a path with three levels: `a`, `b`, and `c`. The value associated with this path contributes to the values of `a`, `a.b`, and `a.b.c`. Your task is to write a function that takes a list of paths and their corresponding values as input, and returns a dictionary (or hash map) where the keys are the full paths of the leaf nodes and the values are the aggregated values for those leaf nodes. Input: A list of strings representing paths and a list of integers representing the values associated with each path. The i-th string in the path list corresponds to the i-th integer in the value list. Output: A dictionary (or hash map) where the keys are the full paths of the leaf nodes and the values are the aggregated values for those leaf nodes.

Examples

Example 1:
Input: {"paths":["a.b.c","a.b","a"],"values":[1,2,3]}
Output: {"a.b.c":6}
Explanation: The value of 'a' (3) contributes to 'a.b.c'. The value of 'a.b' (2) contributes to 'a.b.c'. The value of 'a.b.c' (1) contributes to 'a.b.c'. Therefore, the total value for 'a.b.c' is 3 + 2 + 1 = 6.
Example 2:
Input: {"paths":["x.y","x.z","x"],"values":[4,5,6]}
Output: {"x.y":10,"x.z":11}
Explanation: The value of 'x' (6) contributes to 'x.y' and 'x.z'. The value of 'x.y' (4) contributes to 'x.y'. The value of 'x.z' (5) contributes to 'x.z'. Therefore, the total value for 'x.y' is 6 + 4 = 10, and the total value for 'x.z' is 6 + 5 = 11.
Example 3:
Input: {"paths":["a","a.b","a.b.c","d"],"values":[10,5,2,8]}
Output: {"a.b.c":17,"d":8}
Explanation: The value of 'a' (10) contributes to 'a.b.c'. The value of 'a.b' (5) contributes to 'a.b.c'. The value of 'a.b.c' (2) contributes to 'a.b.c'. The value of 'd' (8) only contributes to 'd'. Therefore, the total value for 'a.b.c' is 10 + 5 + 2 = 17, and the total value for 'd' is 8.

Constraints

  • 1 ≤ number of paths ≤ 1000
  • 1 ≤ length of each path ≤ 100
  • 1 ≤ value of each entry ≤ 1000
  • Paths are case-sensitive
  • Paths will only contain lowercase letters and dots