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);
}
}
5ms JAVA DFS Solution


@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)
.