Java short clean code no stack


  • 1

    I used to use a stack for solving this problem. After reading this post, I'm inspired and think this is a really more intuitive way for this problem. Code is really concise and short.

    So the main idea is that: for a expression string like this:

    T ? A : B -> what we need to do is to select either A or B as a temporary result. This temp result will be added to the input for next iteration. We need to remove all the other characters (e.g. here we need to remove T, ?, A, :, B) after we know the temp result(A)... So that A is to be added to the input and then we start from there again until there is only one single char left.

    The input string will be updated in each iteration and in the last iteration, there is only one char left which is the final result.

    public static String parse(String expression){
    	  if(expression == null || expression.isEmpty()) return "";
    	  String input = expression;
    	  int i = input.length()-1;
    	  //final result will always be a single character
    	  while(input.length() > 1){
    		  while(input.charAt(i) != '?'){
    			  i--;
    		  }
    		  //the first ? is found
    		  char trueOrFalse = input.charAt(i-1);
    		  //compose new input string by adding the middle to original string
    		  char middle = trueOrFalse == 'T' ? input.charAt(i+1) : input.charAt(i+3);
    		  input = input.substring(0,i-1) + middle + input.substring(i+4);
    		  i -= 2;
    	  }
    	  return input;
    	
    }
    

  • 0
    D

    Hi, what is the time complexity


Log in to reply
 

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