Java simple recursion, very to understand


  • 0
    A
        class Solution {
        public String parseTernary(String expression) {
            // algorithm 2017/09/03: recursion is the way to go. How to split into reduced problem?
            //  and what is the termination condition?
            // Observation: each '?' has a matching ':', very much open '(' and close ')'
            //  when nested, we find the matching pair
    
            // The question said that we can always assume the expression is valid
            if (null == expression) {
                return null;
            }
            int strLen = expression.length();
            if (0 == strLen) {
                return "";
            }
    
            int firstQ = expression.indexOf('?');
            if (firstQ < 0) {
                return expression;      // could be: T / F / number
            }
            String condition = expression.substring(0, firstQ);
    
            // find the matching ':'
            int countQs = 1;
            int index   = firstQ + 1;
            for (; index < strLen; index++) {
                char ch = expression.charAt(index);
                if ('?' == ch) {
                    countQs++;
                } else if (':' == ch) {
                    countQs--;
                    if (0 == countQs) {
                        break;
                    }
                }
            }
    
            if (index == strLen) {
                // has ?, but cannot find the matching ':'. This is an invalid expression
                return "";
            }
    
            String truePortion  = expression.substring(firstQ+1, index);
            String falsePortion = expression.substring(index+1);
    
            if ("T".equals(condition)) {
                return parseTernary(truePortion);
            } else if ("F".equals(condition)) {
                return parseTernary(falsePortion);
            } else {
                return "";
            }
        }
    }

Log in to reply
 

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