Problem overview
The function encoded_tree_sums receives a tree written as a string and returns another string in the same format, where every node holds the sum of its whole subtree. In the encoding, a node is its number, optionally followed by its children in curly braces and separated by commas. So 1{2{3,4},5{6}} is a root 1 with two children: 2, which has children 3 and 4, and 5, which has the single child 6.
The subtree sums are 3 and 4 for the leaves, 2 + 3 + 4 = 9 for the first child, 5 + 6 = 11 for the second, and 1 + 9 + 11 = 21 for the root. The answer is 21{9{3,4},11{6}}. A second example: 1{1,1{1,1,1},1} becomes 7{1,4{1,1,1},1}.
Approach: parse and sum in one recursive pass
The string's structure is recursive. A group of siblings is a comma-separated list of nodes, and each node may hold a group of siblings inside braces. That suggests a recursive parser with one function for a group of siblings.
The function reads a group from the current position and stops after the closing } (or at the end of the string). It returns two things: the total of the group's subtree sums, and the group re-encoded as a string. A node's new value is its own number plus the total returned for its children. A leaf has no children, so its value stays as it was.
There is no need to build a tree in memory. The parser rewrites the text as it reads it, and the position in the string is shared between all the recursive calls through a mutable index.
Step by step
The lesson's solution is split into three functions.
encoded_tree_sumssets up the parse. It turns the input into aVec<char>so characters can be reached by position, starts the index at 0, and callsparse_tree. The root is a group of one node, so the string half of the result is the answer, and the sum is dropped.parse_intreads a number. Starting at the index, it multiplies the value by 10 and adds each digit it meets, moving the index forward, until the next character is not a digit. The result is ani64.parse_treekeeps one slot per sibling.valuesholds each sibling's running value andstringsholds the encoded children of each sibling. Both start with one slot, andcurpoints at the current one.- Read the first number into
values[cur]. - Loop over the characters and act on each:
{starts the children of the current node. Skip the brace, callparse_treerecursively, add the returned sum tovalues[cur]and store the returned string instrings[cur].}ends this group. Skip the brace and leave the loop. The caller continues after it.,starts the next sibling. Add a new slot to both vectors, movecurto it and skip the comma.- Anything else must be a number. Read it with
parse_intand add it tovalues[cur].
- Build the output for the group. For each slot, write the value, and if the node has children, append the children's string in braces. Join the parts with commas.
- Return the pair of the group total (the sum of
values) and the joined string.
The solution in Rust
impl Solution {
fn encoded_tree_sums(input: String) -> String {
let chars: Vec<char> = input.chars().collect();
let mut idx = 0usize;
let (_, result) = Self::parse_tree(&chars, &mut idx);
result
}
fn parse_int(chars: &[char], idx: &mut usize) -> i64 {
let mut v: i64 = 0;
while *idx < chars.len() && chars[*idx].is_ascii_digit() {
v = v * 10 + (chars[*idx] as i64 - '0' as i64);
*idx += 1;
}
v
}
fn parse_tree(chars: &[char], idx: &mut usize) -> (i64, String) {
let mut values: Vec<i64> = vec![0];
let mut strings: Vec<String> = vec![String::new()];
let mut cur = 0usize;
values[cur] += Self::parse_int(chars, idx);
while *idx < chars.len() {
match chars[*idx] {
'{' => {
*idx += 1;
let (child_sum, child_str) = Self::parse_tree(chars, idx);
values[cur] += child_sum;
strings[cur] = child_str;
}
'}' => {
*idx += 1;
break;
}
',' => {
cur += 1;
values.push(0);
strings.push(String::new());
*idx += 1;
}
_ => {
let v = Self::parse_int(chars, idx);
values[cur] += v;
}
}
}
let mut parts: Vec<String> = Vec::new();
for i in 0..values.len() {
let mut part = values[i].to_string();
if !strings[i].is_empty() {
part.push('{');
part.push_str(&strings[i]);
part.push('}');
}
parts.push(part);
}
let total: i64 = values.iter().sum();
(total, parts.join(","))
}
}
The Rust details worth a closer look:
- A shared position through
&mut usize. The index is one variable owned byencoded_tree_sums. Each call receives a mutable reference to it, and*idx += 1changes the original, so after a recursive call returns, the caller continues exactly where the callee stopped. Inside the callees,idxis passed on as it is. Reading the value takes*idx. Vec<char>instead of the string. A RustStringis UTF-8 bytes, and indexing it by position isn't allowed. Collectingchars()into a vector gives constant-time access by position.&charsbecomes the slice&[char]automatically.- Digit arithmetic.
chars[*idx] as i64 - '0' as i64casts acharto its numeric code and subtracts the code of'0', which gives the digit's value. Doing the sums ini64keeps larger totals from overflowing, which in ani32would wrap silently in an optimized build. matchon a character. Each arm is a pattern. The last arm,_, catches every other character. Every arm in thismatchevaluates to(), so the arms agree in type.- Tuples.
parse_treereturns(i64, String).let (_, result) = ...destructures it and_throws the sum away. - Summing with
iter().sum(). The annotationlet total: i64tells Rust which type to sum into.
Complexity
Let L be the length of the input.
Time: O(L). Each character is consumed once by the parser. Each group builds its output string once, and every piece of text is copied up through the levels of nesting that enclose it, so for very deeply nested input the copying can grow beyond L, up to O(L * d) for nesting depth d. For typical inputs this is close to linear.
Space: O(L). The character vector, the strings and the vectors of one group each stay proportional to the input, and the recursion depth equals the nesting depth of the tree.
Edge cases and common mistakes
- A single node.
7returns7, because the node has no children to add. - Multi-digit numbers.
10{20,30}returns60{20,30}. Reading one character as one number would break this, which is whyparse_intloops. - Deep nesting.
1{2{3{4}}}returns10{9{7{4}}}. Each level's sum includes everything below it, not only its direct children's original values. - Using original child values instead of child sums. The parent's new value is its own number plus the sums of its children. Adding only the children's original numbers would give the root of
1{2{3,4},5{6}}the value 1 + 2 + 5 = 8 instead of 21. - Leaving leaves untouched. A leaf prints its own number with no braces, since its string is empty.
- Not advancing the index. Any branch of the loop that skips an update to
*idxrepeats forever on the same character. - Empty input. The parser finds no digits and treats it as a node worth 0, so it returns
0.
Testing
1{2{3,4},5{6}}gives21{9{3,4},11{6}}.1{1,1{1,1,1},1}gives7{1,4{1,1,1},1}.7gives7.10{20,30}gives60{20,30}.1{2{3{4}}}gives10{9{7{4}}}.
