Problem overview
The method encodedTreeSums receives a tree written as a string and returns a string in the same format, where every node's number is replaced by the sum of all values in its subtree, the node included.
The format is: a node is its number, optionally followed by its children in braces and separated by commas. So "1{2{3,4},5{6}}" is a root 1 with two children, 2 (with children 3 and 4) and 5 (with the child 6). A node can have any number of children, not just two. Subtree sums are 3 and 4 for the leaves, 2 + 3 + 4 = 9 for the node 2, 5 + 6 = 11 for the node 5 and 1 + 9 + 11 = 21 for the root, so the output is "21{9{3,4},11{6}}".
The second example, "1{1,1{1,1,1},1}", shows a node with three children, one of which has three children of its own. The answer is "7{1,4{1,1,1},1}".
Approach: parse and sum in the same pass
The string is a recursive structure: a node contains a list of nodes. A recursive function that reads one node from the current position handles it naturally. Reading a node means reading its number, and then, if the next character is {, reading child nodes until the closing }.
The function has two results to give back: the node's subtree sum, which its parent needs, and the node's text with the sums substituted, which is what goes into the output. Each call returns both as a tuple. A leaf returns its own value and the same digits. An inner node adds its children's sums to its own value, and builds its text from its new total followed by the already rewritten children in braces.
No tree objects are needed, since each call returns the finished text for its subtree. The only state shared between calls is the current position in the input, which every call advances as it consumes characters.
Step by step
- Turn the string into an array of characters with
Array(input). A SwiftStringcan't be indexed with an integer, but an[Character]can. - Keep the position in a variable
indexthat starts at 0, and pass it to the parser as aninoutargument, so that every recursive call reads from, and advances, the same position. - Return the string part of the parser's result. The tuple's
.1is the encoded tree; the sum.0of the whole tree is not needed. - Read the number. While the current character is a digit, multiply
valueby 10 and add the digit. This supports numbers with several digits, such as 20 or 100. - Start
totalatvalue, and prepare an empty arraychildrenfor the rewritten children. - Check for
{. If it is there, skip it and parse children. If not, the node is a leaf and nothing more is read. - Parse each child with a recursive call. Add its sum to
totaland keep its text inchildren. - Look at the separator. A
,means another child follows: skip it and continue the loop. A}ends the list: skip it and leave the loop. - Build the text. Start from
String(total). If there are children, add{, the children joined with commas, and}. - Return the pair of the total and the text.
The solution in Swift
class Solution {
func encodedTreeSums(_ input: String) -> String {
let chars = Array(input)
var index = 0
return parseEncodedTree(chars, &index).1
}
func parseEncodedTree(_ chars: [Character], _ index: inout Int) -> (Int, String) {
var value = 0
while index < chars.count && chars[index].isNumber {
value = value * 10 + chars[index].wholeNumberValue!
index += 1
}
var total = value
var children = [String]()
if index < chars.count && chars[index] == "{" {
index += 1
while true {
let (childSum, childTree) = parseEncodedTree(chars, &index)
total += childSum
children.append(childTree)
if index < chars.count && chars[index] == "," {
index += 1
continue
}
if index < chars.count && chars[index] == "}" {
index += 1
}
break
}
}
var encoded = String(total)
if !children.isEmpty {
encoded += "{" + children.joined(separator: ",") + "}"
}
return (total, encoded)
}
}
Swift details worth knowing:
- Tuples as return values. The return type
(Int, String)bundles two values, andlet (childSum, childTree) = ...takes the pair apart in one line. The caller ofparseEncodedTreeinencodedTreeSumsreads the second element with.1. inoutposition. The callparseEncodedTree(chars, &index)passes the variable by reference, so a child call that advancesindexadvances it for its parent too. Withoutinouteach call would work on its own copy and the parent would read the same characters again.Character.isNumberandwholeNumberValue.isNumberis true for digits and also for other numeric characters, such as fractions;wholeNumberValuegives the digit as anInt?, which the code unwraps with!. For an input of plain ASCII digits, as here, they are safe.- Comparing with
"{". The elements ofcharsareCharacters, so the string literal is inferred as aCharacterin the comparisonchars[index] == "{". - Bounds checks come first. Each test begins with
index < chars.count && .... The&&operator stops at the first false operand, so the array is never indexed past its end. joined(separator:)glues the array of strings with a comma between neighbours and nothing at either end.
Complexity
Let n be the length of the input.
Time: O(n * d), where d is the nesting depth. Every input character is read once, but each node builds its text from its children's text, so a character of a deep node's text is copied once per ancestor. For a shallow or balanced tree d is small; for a chain nested as deep as the input allows, the copying approaches O(n²).
Space: O(n). The character array holds the input, the returned strings hold the output, and the recursion goes as deep as the tree is nested.
Edge cases and common mistakes
- A single leaf.
"7"returns"7". - Multi-digit numbers. The input
"10{20,30{40}}"gives"100{20,70{40}}". Reading one digit at a time would break it. - Many children. The loop keeps reading children while it sees commas, so a node can have any number of them.
- Empty input. An empty string gives
"0"with this solution, since no digits are read and the value stays 0. The lesson's inputs are never empty. - Not advancing the position. Forgetting to skip
{,,or}leaves the next call on a punctuation character: it reads no digits, so it returns a wrong value of 0 and the output is garbled. - Output the original number. The text must use the new total, not
value. Leaves are the only nodes where the two are equal. - Adding the children's text instead of the sum. The tuple keeps the two apart: the sum goes up into
total, and the text goes intochildren.
Testing
"1{2{3,4},5{6}}"gives"21{9{3,4},11{6}}"."1{1,1{1,1,1},1}"gives"7{1,4{1,1,1},1}"."7"gives"7"."10{20,30{40}}"gives"100{20,70{40}}".
