Java 8ms O(n) recursive solution


  • 0
    public String parseTernary(String expression) {
        return helper(expression);
    }
    public String helper(String expression){
        if(expression.length()==1) return expression;
        Stack<Integer> mark = new Stack<>(); // The type of stack does not matter, just to see if there is still some '?' which                    can make the current ':' a pair.
        int i = 2;//assume the expression is always valid, skip the first '?'.
        int cut = 0; //used to record the position of ':' with respect to the first 'T' or 'F' of the current expression
        while(true){
            if(expression.charAt(i)=='?'){
                    mark.push(i);
            }
            if(expression.charAt(i)==':'){
                if(!mark.empty()){
                    mark.pop();
                }
                else{
                    cut = i;
                    break;
                }
            }
            i++;
        }            
        if(expression.charAt(0)=='T'){
            return helper(expression.substring(2,cut));
        } 
        else{
            return helper(expression.substring(cut+1,expression.length()));
        }
    }

Log in to reply
 

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