C++ iterative solution, no recursion, no stack O(n) time O(1) space


  • 0
    E
    class Solution {
    public:
        
        string parseTernary(string expression) {
            int start = 0;
            int end = expression.length();
            while(start < end-1)
            {
                // T?....:....
                // ^          ^
                // start      end
                auto cond = expression[start] == 'T';
                int colonPos = start;
                int counter = 0;
                do
                {
                    colonPos++;
                    if(expression[colonPos] == '?')
                        ++counter;
                    else if(expression[colonPos] == ':')
                        --counter;
                }while(counter != 0);
                // T?....:....
                // ^     ^      ^
                //       colonPos
                
                if(cond)
                {
                    start +=2;
                    end = colonPos;
                    // T?.......:....
                    //   ^      ^
                    //   start  end
                }
                else
                {
                    start = colonPos+1;
                    // T?.......:........
                    //           ^       ^
                    //           start   end
                }
            }
            string res;
            res.push_back( expression[start] );
            return res;
        }
    };
    

Log in to reply
 

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