Straightforward Java solution with explanation and a simple implementation of NestedInteger for your ease of testing


  • 15

    Also viewable here.

    The idea is very straightforward:

    1. if it's '[', we just construct a new nested integer and push it onto the stack

    2. if it's a number, we parse the whole number and add to the previous nested integer object

    3. if it's ',', we'll just continue;

    4. if it's ']', we'll just pop one nested integer from the working stack and assign it to the result

    Also, we'll pay attention to this corner case or understand the input: the input could be "324", "[324]", they are different: the former should return a nested integer with one single integer, the latter should return a nested integer with a list

    public NestedInteger deserialize(String s) {
            if(s == null || s.isEmpty() || s.length() == 0) return new NestedInteger();
            Stack<NestedInteger> workStack = new Stack<NestedInteger>();
            NestedInteger result = null;
            StringBuilder sb = new StringBuilder();
            int i = 0;
            //if it's just a single number, then we'll just return a nested integer with one integer
            if(s.charAt(i) != '['){
                sb.setLength(0);
                while(i < s.length() && ((Character.getNumericValue(s.charAt(i)) < 10 && Character.getNumericValue(s.charAt(i)) >= 0) || s.charAt(i) == '-')){
                    sb.append(s.charAt(i));
                    i++;
                }
                int num = Integer.parseInt(sb.toString());
                return new NestedInteger(num);
            }//all other cases, we'll return a nested integer with a list
            else{
                while (i < s.length()) {
                    if (s.charAt(i) == '[') {
                        NestedInteger ni = new NestedInteger();
                        // we'll put this one into its last one if there's one on the workStack
                        if (!workStack.isEmpty()) {
                            NestedInteger lastNi = workStack.pop();
                            lastNi.add(ni);
                            workStack.push(lastNi);// then push it back
                        }
                        workStack.push(ni);
                        i++;
                    } else if (s.charAt(i) == ',') {
                        i++;
                    } else if (s.charAt(i) == ']') {
                        NestedInteger completedNi = workStack.pop();
                        result = completedNi;
                        i++;
                    } else {
                        // then it must be a number
                        sb.setLength(0);
                        while (i < s.length()
                                && ((Character.getNumericValue(s.charAt(i)) < 10 && Character
                                        .getNumericValue(s.charAt(i)) >= 0) || s.charAt(i) == '-')) {
                            sb.append(s.charAt(i));
                            i++;
                        }
                        int num = Integer.parseInt(sb.toString());
                        NestedInteger ni = null;
                        if (!workStack.isEmpty())
                            ni = workStack.pop();
                        else
                            ni = new NestedInteger();
                        // case 1: if this one contains one integer
                        if (ni.isInteger()) {
                            // we'll add it to this ni
                            ni.add(new NestedInteger(num));
                        }
                        // case 2: if this one contains a nested integer
                        else if (ni.getList() != null && ni.getList().size() != 0) {
                            // we'll get the last nested integer and add this one to it
                            ni.add(new NestedInteger(num));
                        } else {
                            // case 3: if this is an empty nested integer
                            if(i > 0) ni.add(new NestedInteger(num));
                            else ni.setInteger(num);
                        }
                        workStack.push(ni);
                        if (i == s.length())
                            return ni;// this is for test cases like this: "324", there's no '[' or ']'
                    }
                }
            }
            return result;
        }
    

    Also, I've written a simple implementation for NestedInteger class, I find it helpful, posted it here as well:

    class NestedInteger {
        private List<NestedInteger> list;
        private Integer integer;
        
        public NestedInteger(List<NestedInteger> list){
            this.list = list;
        }
        
        public void add(NestedInteger nestedInteger) {
            if(this.list != null){
                this.list.add(nestedInteger);
            } else {
                this.list = new ArrayList();
                this.list.add(nestedInteger);
            }
        }
    
        public void setInteger(int num) {
            this.integer = num;
        }
    
        public NestedInteger(Integer integer){
            this.integer = integer;
        }
    
        public NestedInteger() {
            this.list = new ArrayList();
        }
    
        public boolean isInteger() {
            return integer != null;
        }
    
        public Integer getInteger() {
            return integer;
        }
    
        public List<NestedInteger> getList() {
            return list;
        }
        
        public String printNi(NestedInteger thisNi, StringBuilder sb){
            if(thisNi.isInteger()) {
                sb.append(thisNi.integer);
                sb.append(",");
            }
            sb.append("[");
            for(NestedInteger ni : thisNi.list){
                if(ni.isInteger()) {
                    sb.append(ni.integer);
                    sb.append(",");
                }
                else {
                    printNi(ni, sb);
                }
            }
            sb.append("]");
            return sb.toString();
        }
    }
    
    

  • 2
    I

    Thanks a lot for your implementation of NestedInteger, I solve this problem much faster using your code


Log in to reply
 

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