JAVA, recursive method, with detailed explaining 3ms


  • 0
    public class Solution {
        /*
         * Thoughtway: 
         * Decode the string is to unzip the compressed part of the input string.
         * e.g. a2["content"]c ==> a"content""content"c 
         * and "content" may go through the same process to get the pure string.
         * 
         * Method: (Recursive: easy to code, but takes more stack memory)
         * Scan the input string from index 0 to the end and append characters into the result.
         * When encountering a digit : 
         *  1 parse the real value represents by it and its following digits, say "repeat" times. 
         *  2 find the index of the closing bracket corresponding to the open braket following the last digit in step 1
         *      e.g. 8[3[hello]world] : the ']' folloing "world" is the closing bracket of '[' following 8
         *  3 decode the substring between open and closing brackets by calling "decodeString", say "content"
         *  4 append "content" to result "repeat" times
         *  5 keep going to the end
         * 
         
         * Analysis :
         * real performance : 3ms
         * in the worst case : time O(n2) space O(n2)
         */
        public String decodeString(String s) {
            int len = s.length();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < len; i ++) {`
                char ch = s.charAt(i);
                if (Character.isLetter(ch)) {
                    sb.append(ch);
                } else if (Character.isDigit(ch)) {
                    int start = i;
                    while (i + 1 < len && Character.isDigit(s.charAt(i + 1))) {
                        i ++;
                    }
                    int repeatTime = Integer.parseInt(s.substring(start, i + 1));
                    int openLeft = 1;
                    i = i + 2;
                    start = i;
                    while (openLeft != 0) {
                        if (s.charAt(i) == '[') {
                            openLeft ++;
                        } else if (s.charAt(i) == ']') {
                            openLeft --;
                        }
                        i ++;
                    }
                    i --;
                    String repeatStr = decodeString(s.substring(start, i));
                    while (repeatTime -- > 0) {
                        sb.append(repeatStr);
                    }
                }
            }
            return sb.toString();
        }
    }
    

Log in to reply
 

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