TreesAndBrackets
SRM 731 · 2018-03-16 · by subscriber
SRM 731 · 2018-03-16 · by subscriber · Dynamic Programming, String Manipulation
Problem Statement
Problem Statement
This problem is about rooted trees in which the order of children matters.
This type of trees is easily encoded using correct bracket sequences.
The code of a tree rooted at r is constructed as follows:
String s t1 and t2 that represent two rooted trees using the encoding defined above.
You want to transform t1 into t2.
The only operation you are allowed to perform is to remove a leaf from t1. (A leaf is a vertex with no children.) Note that removing the child of a parent does not change the relative order of the other children of that same parent.
Return "Possible" if there is a sequence of zero or more operations that transforms t1 into t2. Otherwise, return "Impossible".
- Write down the opening bracket '('.
- For each child c of r, in order, write down the code of the subtree rooted at c.
- Write down the closing bracket ')'.
The only operation you are allowed to perform is to remove a leaf from t1. (A leaf is a vertex with no children.) Note that removing the child of a parent does not change the relative order of the other children of that same parent.
Return "Possible" if there is a sequence of zero or more operations that transforms t1 into t2. Otherwise, return "Impossible".
Constraints
- t1 and t2 will contain between 2 and 100 characters, inclusive.
- Each character in t1 and t2 will be either '(' or ')'.
- Both t1 and t2 will represent a correct tree.
Examples
0)
"(())" "()" Returns: "Possible"
1)
"()" "()" Returns: "Possible"
2)
"(()()())" "((()))" Returns: "Impossible"
Currently t1 is a tree of depth 2 in which the root has three children, while t2 is a tree of depth 3. Clearly, you cannot increase the depth of a tree by removing some of its vertices.
3)
"((())((())())())" "(()(())())" Returns: "Possible"
4)
"((())((())())())" "((()()()()()))" Returns: "Impossible"
Submissions are judged against all 112 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TreesAndBrackets with a public method string check(string t1, string t2) · 112 test cases · 2 s / 256 MB per case