[C++ Recursive] with short explanation


  • 0
    H
    class Solution {
    public:
        /// Add integers in range [left, right] to the res NestedInteger.
        void parseIntegers (const string &s, int left, int right, NestedInteger &res) {
            if (left > right) return ;
            
            int num = 0;
            /// If we have unprocessed number.
            bool val = false;
            /// If the current number is negative.
            bool neg = false;
            
            /// A simple version of state machine to parse numbers.
            for (int i = left; i <= right; ++i) {
                if (s[i] == '-') {
                    num = 0;
                    neg = true;
                } else if (s[i] == ',') {
                    if (val) res.add(NestedInteger(num));
                    num = 0;
                    val = false;
                    neg = false;
                } else {
                    if (neg) num = num * 10 - (s[i] - '0');
                    else num = num * 10 + (s[i] - '0');
                    val = true;
                }
            }
            if (val) res.add(NestedInteger(num));
        }
    
        NestedInteger parseNestedInteger (const string &s, int left, int right) {
            if (left > right) return NestedInteger();
            else if (s[left] != '[' || s[right] != ']') return NestedInteger(stoi(s));
            
            NestedInteger res;
            int lastpos = left + 1;
            for (int i = left + 1; i <= right - 1; ++i) {
                if (s[i] == '[') {
                    /// Parse and add the (unprocessed) numbers before the nested structure.
                    parseIntegers(s, lastpos, i - 1, res);
                    
                    /// Find the matched [] in the string, and parse this structure recursively.
                    int leftcounter = 1, j = i;
                    while (leftcounter != 0) {
                        ++j;
                        if (s[j] == '[') ++leftcounter;
                        else if (s[j] == ']') --leftcounter;
                    }
                    res.add(parseNestedInteger(s, i, j));
                    i = j + 1;
                    
                    lastpos = i;
                }
            }
            parseIntegers(s, lastpos, right - 1, res);
            
            return res;
        }
    
        NestedInteger deserialize(string s) {
            return parseNestedInteger(s, 0, s.size() - 1);
        }
    };
    

Log in to reply
 

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