Java 3ms recursive solution, no stack


  • 0
    Z
    public class Solution {
        public String decodeString(String s) {
            return explore(s, 0, s.length());
        }
        
        String explore(String s, int start, int end) {
            if (start >= end) return "";
            int time = 0;
            int i = start;
            //calculate repeating time
            while (i < end && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                time = time * 10 + (int)(s.charAt(i++)-'0');
            }
            StringBuilder sb = new StringBuilder();
            int nextstart = i;
            if (time == 0) {
                //don't need to repeat
                while (i < end && (s.charAt(i) >= '9' || s.charAt(i) <= '0')) {
                    sb.append(s.charAt(i++));
                }
            } else {
                int cntBracket = 1;
                i++;
                int newstart = i;
                while (i < end && cntBracket > 0) {
                    if (s.charAt(i) == ']') {
                        --cntBracket;
                    } else if (s.charAt(i) == '[') {
                        ++cntBracket;
                    }
                    i++;
                }
                String inside = explore(s, newstart, i-1);
                //repaet the inside string
                while (time-- > 0) {
                    sb.append(inside);
                }
            }
            sb.append(explore(s, i, end));
            return sb.toString();
            
            
        }
    }
    

Log in to reply
 

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