My Java DFS solution, similar to Decoding String.


  • 0
    K
     public NestedInteger deserialize(String s) {
            NestedInteger res = new NestedInteger();
            if(s == null || s.length() == 0) return res;
            dfs(s, 0, res);
            List<NestedInteger> tmpList = res.getList();
            return tmpList.get(0);
        }
        
        // This will return the index that has been processed by next level
        private int dfs(String s, int start, NestedInteger parent) {
            if(start > s.length()) return s.length();
            
            for(int i = start; i < s.length();) {
                // If its ']' means need to get to the previous layer
                if(s.charAt(i) == ']') {
                    return i + 1;
                }
                
                // Find the integer part and add it to 
                if(s.charAt(i) == ',') {
                    i++;
                } else if(s.charAt(i) != '[') {
                    boolean negative = false;
                    if(s.charAt(i) == '-') {
                        negative = true;
                        i++;
                    }
                    int tmp = i;
                    while(tmp < s.length() && Character.isDigit(s.charAt(tmp))) {
                        tmp++;
                    }
                    //System.out.println("i--> " + i +"tmp---> " + tmp);
                    int intPart = Integer.parseInt(s.substring(i,tmp)); 
                    parent.add(new NestedInteger(negative ? -intPart : intPart));
                    i = tmp;
                } else {
                     NestedInteger curr = new NestedInteger();
                     int nextI = dfs(s, i+1, curr);
                     parent.add(curr);
                     i = nextI;
                }
            }
            
            return s.length();
        }
    

Log in to reply
 

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