Mini Parser

This approach leverages recursion, which is a natural fit for parsing nested or tree-like data structures. The function calls itself to handle nested lists, effectively performing a depth-first traversal of the nested structure represented by the string.

• The core idea is to use a recursive helper function that parses a portion of the string and advances a global or passed-by-reference index.
• The main deserialize function checks if the string represents a single number (i.e., does not start with [). If so, it parses it and returns.
• Otherwise, it calls a recursive helper function to parse the list.
• The recursive helper function, say parse(s, index):
  • If the character at the current index is '[', it knows it's parsing a list. It creates a new NestedInteger list.
  • It then enters a loop, continuing as long as the character at the index is not ']'. Inside the loop, it recursively calls parse to get the next element (which could be a number or another list) and adds it to the current list.
  • It handles commas by simply advancing the index.
  • Once it hits ']', it advances the index past it and returns the created list.
  • If the character at the current index is a digit or a '-', it knows it's parsing a number. It reads all consecutive digits to form the number string, parses it to an integer, creates a NestedInteger with this value, and returns it.

We can design a recursive function that is responsible for parsing one NestedInteger element from the string, starting at a given index. Since we need to keep track of our progress through the string across recursive calls, we can pass an index by reference (e.g., using a single-element array int[]) or use a class member for the index.

The base case for the recursion is a number. If the substring to be parsed does not start with '[', we parse it as an integer.

The recursive step handles lists. If the substring starts with '[', we create a new NestedInteger to act as a list. We then iterate, recursively calling the function to parse each element within the brackets until we encounter the closing ']'. Commas are used as delimiters to separate elements.

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // 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();
 * }
 */
class Solution {
    private int index = 0;

    public NestedInteger deserialize(String s) {
        // If the string doesn't start with '[', it's a single integer.
        // This check is implicitly handled by the logic below.
        return parse(s);
    }

    private NestedInteger parse(String s) {
        if (s.charAt(index) == '[') {
            index++; // Skip '['
            NestedInteger ni = new NestedInteger();
            while (s.charAt(index) != ']') {
                ni.add(parse(s));
                if (s.charAt(index) == ',') {
                    index++; // Skip ','
                }
            }
            index++; // Skip ']'
            return ni;
        } else {
            // It's a number
            int start = index;
            while (index < s.length() && (Character.isDigit(s.charAt(index)) || s.charAt(index) == '-')) {
                index++;
            }
            int num = Integer.parseInt(s.substring(start, index));
            return new NestedInteger(num);
        }
    }
}