6ms JAVA solutions without Stack


  • 0

    Since the expression is always valid, so we don't need to consider too much about the invalid cases or the boundary problems. The idea is :

    When we travel the string from index 0, it always starts with 'T' or 'F'. if value of the pointer(pos in code) is 'T', we could safely jump it by pos +=2. Otherwise we use a jump function to jump the pointer to next fit one. now the new pointer might point to a number(then end the while loop), or a nested ternary expressions(then loop in the while block), or a 'F' or 'T' to be return(who are not followed by '?' )

    So how to implement the jump function? For example, if the expression we will deal with is F?1:T?4:5, and pos = 0, we need pass the same number of '?' and ':' with the same idea of
    parentheses problem.

    Here is the code:

    public class Solution {
        int pos;
        public String parseTernary(String exp) {
            pos = 0; 
            while(exp.charAt(pos) == 'T' || exp.charAt(pos) == 'F'){
                if(pos == exp.length() - 1 || exp.charAt(pos + 1) != '?'){
                    return String.valueOf(exp.charAt(pos));
                }
                
                if(exp.charAt(pos) == 'F'){
                    jump(exp);
                }
                else{
                    pos+=2;   
                }
            }
            
            return String.valueOf(exp.charAt(pos));
        }
        
        public void jump(String exp){
            int count = 1;
            pos += 2;
            while(count > 0){
                if(exp.charAt(pos) == '?'){
                    count++;
                }
                if(exp.charAt(pos) == ':'){
                    count--;
                }
                pos++;
            }
        }
    }
    

Log in to reply
 

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