Sharing two C++ solutions: one pass 12ms solution and DFS 6ms solution


  • 0
    C

    1. One pass solution:
    Time complexity: O(n)
    The ternary expression is essentially a pre-order DFS of a corresponding binary tree, so the one pass solution is trying to rebuild the tree with the help of a stack.

    Two possible cases:

    Whenever we meet a ?, this means the previous node is a non-leaf node, and we need to update its type.
    Whenever we meet a :, this means the previous node is either a leaf node, and we need to update the leaf value and do a bottom up traversal to connect the children with their parents, and we can update the expression decision on-the-fly.

        struct Node {
            bool hasLeft;
            bool hasRight;
            char type;
            char value;
            Node() : type(-1), value(-1), hasLeft(false), hasRight(false) {};
        };
        string parseTernary(string expression) {
            vector<Node> roots;
            roots.push_back(Node());
            
            for (int i=0; i<=expression.size(); i++) {
                char c = i == expression.size() ? ':' : expression[i];
                if (c == '?') {
                    roots.back().type = expression[i-1];
                    roots.push_back(Node());
                } else if (c == ':') {
                    roots.back().hasLeft = true;
                    roots.back().hasRight = true;
                    roots.back().value = expression[i-1];
                    while (roots.size() > 1 && roots.back().hasLeft && roots.back().hasRight) {
                        Node node = roots.back();
                        roots.pop_back();
                        if (!roots.back().hasLeft) {
                            if (roots.back().type == 'T') roots.back().value = node.value;
                            roots.back().hasLeft = true;
                        } else {
                            if (roots.back().type == 'F') roots.back().value = node.value;
                            roots.back().hasRight = true;
                        }
                    }
                    if (i < expression.size()) roots.push_back(Node());
                }
            }
            
            string result;
            result += roots.back().value;
            return result;
        }
    

    2. DFS solution:
    Time Complexity: O(nk) where k is the recursion depth, which can be as bad as k.
    Another way to look at it is that, still a binary tree, but we can at each level decide to go left or right based on the current 'T' or 'F' on the parent node. This is essentially a pre-order traversal again.

    The pre-order traversal works as the following:

    At each level, we need to dive the expression into left child and right child by going over the expression and find out the outermost matching pair of '?' and ':', we can maintain a counter for '?' and increment that when we hit a '?' and decrement when we hit ':' until the counter reaches zero.

    The base case for this DFS is that if there's no subexpression, we can quickly branch out as a leaf (since leaf only contains one char)

    Then call recursion on left child or right child based on the parent value.

        string parseTernary(string expression) {
            if (expression.empty()) return expression;
            char val = evaluateSubExpression(expression, 0, expression.size()-1);
            string result;
            result += val;
            return result;
        }
        
        char evaluateSubExpression(const string& expr, int start, int end) {
            if (start == end) return expr[start];
            int op1 = -1;
            int op2 = -1;
            int depth = 0;
            
            for (int i=start; i <= end; i++) {
                if (expr[i] == ' ') continue;
                if (expr[i] == '?') {
                    depth++;
                    if (op1 == -1) op1 = i;
                } else if (expr[i] == ':') {
                    if ((--depth) == 0) {
                        op2 = i;
                        break;
                    }
                }
            }
            
            if (expr[start] == 'T') {
                return evaluateSubExpression(expr, op1+1, op2-1);
            } else {
                return evaluateSubExpression(expr, op2+1, end);
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.