Java O(n), iterate from left to right with stack


  • 0
    Y

    Many suggested to iterate from right to left, and evaluate whenever a question mark is encountered.
    We can actually also iterate from left to right, and evaluate whenever a colon is encountered, with the help of a stack of course. We also need to push colons onto the stack so that we know how many ternary expressions we can evaluate at a certain point. We don't need to push question marks though.

    public class Solution {
        public String parseTernary(String expression) {
            Stack<Character> stack = new Stack<Character>();
            for (int i=0; i<expression.length(); i++) {
                char ch = expression.charAt(i);
                if (ch == '?') continue;
                if (!stack.isEmpty() && stack.peek() != ':') {
                    // if previous was not colon, we can't evaluate yet - simply push it onto the stack
                    stack.push(ch);
                } else if (i+1 < expression.length() && expression.charAt(i+1) == '?') {
                    // previous was colon, but next is question mark - can't evaluate either
                    stack.push(ch);
                } else {
                    // otherwise, evaluate until we don't peek colon from the stack
                    char c = ch;
                    while (!stack.isEmpty() && stack.peek() == ':') {
                        stack.pop(); // ':'
                        char b = stack.pop(), a = stack.pop();
                        if (a == 'T') c = b;
                    }
                    stack.push(c);
                }
            }
            return String.valueOf(stack.peek());
        }
    }
    

    It's still a O(n) time complexity solution as each character will be at most pushed once. Worst case space complexity would also be O(n).
    The solution is slower compared to solutions iterating from right to left, due to fact that, it's always safe to evaluate an expression when a question mark is encountered.

    Using array to simulate a stack will make it faster:

    public class Solution {
        public String parseTernary(String expression) {
            char[] chars = expression.toCharArray();
            int len = chars.length;
            int index = -1;
            
            for (int i=0; i<len; i++) {
                if (chars[i] == '?') continue;
                if (index >= 0 && chars[index] != ':') {
                    chars[++index] = chars[i];
                } else if (i+1 < len && chars[i+1] == '?') {
                    chars[++index] = chars[i];
                } else {
                    char c = chars[i];
                    while (index >= 0 && chars[index] == ':') {
                        index--; // ':'
                        char b = chars[index--], a = chars[index--];
                        if (a == 'T') c = b;
                    }
                    chars[++index] = c;
                }
            }
            return String.valueOf(chars[0]);
        }
    }
    

Log in to reply
 

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