algoadvance

Leetcode 385. Mini Parser

Problem Statement

The problem 385 on Leetcode is “Mini Parser.”

Given a nested list of integers represented as a string, implement a parser to deserialize it.

Each element is either an integer, a list, or a list of lists, etc. For example, given the string s = "[123,[456,[789]]]", you should return a NestedInteger object containing a structure that corresponds to this list.

Clarifying Questions

  1. What is the structure of NestedInteger class?
    • It is assumed that NestedInteger provides the following methods: 
      // Constructor initializes an empty nested list.
public NestedInteger();

// Constructor initializes a single integer.
public NestedInteger(int value);

// @return true if this NestedInteger holds a single integer, rather than a nested list.
public boolean isInteger();

// @return the single integer that this NestedInteger holds, if it holds a single integer
// Return null if this NestedInteger holds a nested list
public Integer getInteger();

// Set this NestedInteger to hold a single integer.
public void setInteger(int value);

// Set this NestedInteger to hold a nested list and adds a nested integer to it.
public void add(NestedInteger ni);

// @return the nested list that this NestedInteger holds, if it holds a nested list
// Return null if this NestedInteger holds a single integer
public List<NestedInteger> getList();
  2. What are the inputs and constraints?
    • The input is a single string s that represents the nested list.
    • A string may represent:
      • A single integer.
      • A nested list containing integers and/or nested lists.
    • The string is guaranteed to be valid as per problem constraints.
  3. Should we handle negative numbers and spaces?
    • Yes, negative numbers can be present and there can be no spaces in the serialized input.

Strategy

  1. Initialization: Use a stack to help with the nested structure.
  2. Iterating through Characters:
    • If encountering [, a new NestedInteger is created and pushed onto the stack.
    • If encountering ], a NestedInteger is popped from the stack and added to the NestedInteger just below it.
    • If a number is encountered, it could be negative and might span multiple characters, so handle multi-digit numbers.
  3. Final Structure:
    • If the input string does not start with [, it means it’s just a single integer.

Time Complexity

Code

import java.util.Stack;

public class MiniParser {
    public NestedInteger deserialize(String s) {
        if (s == null || s.isEmpty()) {
            return null;
        }
        
        Stack<NestedInteger> stack = new Stack<>();
        NestedInteger current = null;
        int l = 0; // left index of a number substring
        
        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            
            if (c == '[') {
                if (current != null) {
                    stack.push(current);
                }
                current = new NestedInteger();
                l = r + 1;
            } else if (c == ']') {
                String num = s.substring(l, r);
                if (!num.isEmpty()) {
                    current.add(new NestedInteger(Integer.parseInt(num)));
                }
                if (!stack.isEmpty()) {
                    NestedInteger pop = stack.pop();
                    pop.add(current);
                    current = pop;
                }
                l = r + 1;
            } else if (c == ',') {
                if (s.charAt(r - 1) != ']') {
                    String num = s.substring(l, r);
                    current.add(new NestedInteger(Integer.parseInt(num)));
                }
                l = r + 1;
            }
        }
        
        if (current == null) {
            return new NestedInteger(Integer.parseInt(s));
        }
        
        return current;
    }

    // NestedInteger class implementation
    public static class NestedInteger {
        private Integer integer;
        private List<NestedInteger> list;

        public NestedInteger() {
            this.list = new ArrayList<>();
        }

        public NestedInteger(int value) {
            this.integer = value;
        }

        public boolean isInteger() {
            return integer != null;
        }

        public Integer getInteger() {
            return integer;
        }

        public void setInteger(int value) {
            this.integer = value;
        }

        public void add(NestedInteger ni) {
            list.add(ni);
        }

        public List<NestedInteger> getList() {
            return list;
        }
    }
}

This code correctly handles the deserialization of nested lists and individual integers according to the described strategy and constraints.

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