5ms JAVA DFS Solution


  • 17
    B
    public class Solution {
        public String parseTernary(String expression) {
            if(expression == null || expression.length() == 0){
                return expression;
            }
            char[] exp = expression.toCharArray();
            
            return DFS(exp, 0, exp.length - 1) + "";
            
        }
        public char DFS(char[] c, int start, int end){
            if(start == end){
                return c[start];
            }
            int count = 0, i =start;
            for(; i <= end; i++){
                if(c[i] == '?'){
                    count ++;
                }else if (c[i] == ':'){
                    count --;
                    if(count == 0){
                        break;
                    }
                }
            }
            return c[start] == 'T'? DFS(c, start + 2, i - 1) : DFS(c, i+1,end);
        }
    }
    

  • 0
    Z

    Really great!! The beautiful part is you change the expression in String to real expression!!


  • 1

    @binghont
    Similar idea, shorter code:

    public String parseTernary(String expression) {
            if (expression.length()==1) return expression;
            int i=1, count=1;
            while (count !=0){
                char c=expression.charAt(++i);
                count += c=='?' ? 1: c==':'? -1: 0;
            } 
            return expression.charAt(0) == 'T'? parseTernary(expression.substring(2,i)): parseTernary(expression.substring(i+1));
        }
    

    The key idea is to find the legitimate : separating two "values".
    This : has the property that the number of ? ahead of this : should equals the number of :, similar to the case of ( and ).


  • 1
    Z

    Only problem is the time complexity is up to O(n^2) in the worse case.
    For example, T?T?T?T?T?1:2:3:4:5:6.


Log in to reply
 

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