5ms JAVA DFS Solution


  • 19
    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.


  • 0
    F

    Same idea.

    class Solution {
        public String parseTernary(String expression) {
            if (expression == null || expression.length() == 0) {
                return "";
            }
            return dfs(expression, 0, expression.length() - 1);
        }
        public String dfs(String expression, int start, int end) {
            if (start == end) {
                return String.valueOf(expression.charAt(start));
            }
            int count = 1;
            int i = start + 2;
            for (; i <= end; i++) {
                if (expression.charAt(i) == '?') {
                    count++;
                } else if (expression.charAt(i) == ':'){
                    count--;
                }
                if (count == 0) {
                    break;
                }
            }
            if (expression.charAt(start) == 'T') {
                return dfs(expression, start + 2, i - 1);
            }
            return dfs(expression, i + 1, end);
        }
    }
    

Log in to reply
 

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