algoadvance

Leetcode 385. Mini Parser

Problem Statement

The problem is to implement a parser that takes a nested list of integers in the form of a string and returns an instance of the NestedInteger class.

The class NestedInteger has the following interface:

class NestedInteger {
public:
    // Constructor initializes an empty nested list.
    NestedInteger();
    
    // Constructor initializes a single integer.
    NestedInteger(int value);
    
    // Return true if this NestedInteger holds a single integer, rather than a nested list.
    bool isInteger() const;
    
    // Return the single integer that this NestedInteger holds, if it holds a single integer.
    // The result is undefined if this NestedInteger holds a nested list.
    int getInteger() const;
    
    // Set this NestedInteger to hold a single integer.
    void setInteger(int value);
    
    // Set this NestedInteger to hold a nested list and adds a nested integer to it.
    void add(const NestedInteger &ni);
    
    // Return the nested list that this NestedInteger holds, if it holds a nested list.
    // The result is undefined if this NestedInteger holds a single integer.
    const vector<NestedInteger> &getList() const;
};

Given a string s representing a nested list (a combination of integers and lists), implement the function:

NestedInteger deserialize(std::string s);

Clarifying Questions

  1. Input Format:
    • Is the string always valid?
    • Can the string contain negative numbers?
  2. Edge Cases:
    • How should the function behave in case of empty string input?
    • What is the behavior if the input represents a single integer?

Strategy

To deserialize the string representation of the nested list, we can use a stack to keep track of nested structures. Here’s the strategy:

  1. Initialization:
    • If the input string is empty, return a default NestedInteger.
    • If the input string is a single integer, return a NestedInteger initialized with that integer.
  2. Traversal:
    • Use a stack to keep track of current NestedInteger objects.
    • Traverse through each character in the string:
      • If a [ is encountered, start a new NestedInteger list.
      • If a ] is encountered, finalize the current NestedInteger list by popping from the stack and adding to the previous top.
      • If a , is encountered, it indicates the end of a number, so we finalize the number and add it to the current NestedInteger.
      • Handle negative numbers accordingly by checking for -.
  3. Number Extraction:
    • Keep track of positions where numbers start and end.
    • Convert the substring to an integer and create a new NestedInteger initialized with this integer.
  4. Return Value:
    • The entire nested structure will be built in the stack, and the top element at the end will be our required NestedInteger.

Code

class Solution {
public:
    NestedInteger deserialize(std::string s) {
        if (s.empty()) {
            return NestedInteger();
        }
        
        if (s[0] != '[') {
            return NestedInteger(std::stoi(s));
        }
        
        std::stack<NestedInteger> stack;
        NestedInteger curr;
        int n = s.size();
        int numStart = -1;  // to track start index of number
        bool negative = false;

        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (c == '[') {
                if (!stack.empty()) {
                    stack.push(curr);
                }
                curr = NestedInteger();
            } else if (c == ']') {
                if (numStart != -1) {
                    curr.add(NestedInteger(std::stoi(s.substr(numStart, i - numStart))));
                    numStart = -1;
                }
                if (!stack.empty()) {
                    NestedInteger temp = curr;
                    curr = stack.top();
                    stack.pop();
                    curr.add(temp);
                }
            } else if (c == ',') {
                if (numStart != -1) {
                    curr.add(NestedInteger(std::stoi(s.substr(numStart, i - numStart))));
                    numStart = -1;
                }
            } else if (c == '-') {
                negative = true;
                numStart = i;  // start of the number
            } else {  // digit
                if (numStart == -1) numStart = i;  // start of the number
            }
        }

        return curr;
    }
};

Time Complexity

The time complexity of this approach is O(n), where n is the length of the input string s. Each character in the string is processed once, and operations on the stack take constant time. Thus, the overall complexity is linear with respect to the number of characters in the string.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI