Recursive Descent Parsing Solution in Java, Beats 99.53%


  • 0
    Y

    BNF for nested integer:
    <ni> ::= <int> | [<list>]
    <list> ::= <ni> | <ni>,<list>

    public class Solution {
        // <ni> ::= <int> | [<list>]
        // <list> ::= <ni> | <ni>, <list>
        char[] src;
        int pos;
        public NestedInteger deserialize(String s) {
            src = s.toCharArray();
            pos = 0;
            return parseNestedInteger();
        }
        public NestedInteger parseNestedInteger() {
            if (src[pos] == '-' || src[pos] >= '0' && src[pos] <= '9') {
                return parseInt();
            } else {
                pos++; // skip '['
                NestedInteger ni = new NestedInteger();
                while (src[pos] != ']') {
                    ni.add(parseNestedInteger());
                    if (src[pos] == ',') {
                        pos++; // skip ','
                    }
                }
                pos++; // skip ']'
                return ni;
            }
        }
        public NestedInteger parseInt() {
            int flag = 1, num = 0;
            if (src[pos] == '-') {
                flag = -1;
                pos++;
            }
            while (pos < src.length && src[pos] >= '0' && src[pos] <= '9') {
                num = num * 10 + src[pos] - '0';
                pos++;
            }
            return new NestedInteger(flag * num);
        }
    }
    

Log in to reply
 

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