Java recursive solution, really easy to understand


  • 0
    L

    We only need to accumulate the top level [].

    public class Solution {
        public String decodeString(String s) {
            StringBuilder sb = new StringBuilder();
            Deque<Integer> dq = new ArrayDeque<>();
            
            int last = -1;
            for (int i = 0; i < s.length(); i++) {
                if (last < 0 && dq.isEmpty() && !(s.charAt(i) >= '0' && s.charAt(i) <= '9')) {
                    sb.append(s.charAt(i));
                } else if (last < 0 && (s.charAt(i) >= '0' && s.charAt(i) <= '9')) {
                    last = i;
                } else if (s.charAt(i) == '[') {
                    dq.addFirst(i);
                } else if (s.charAt(i) == ']') {
                    int j = dq.removeFirst();
                    if (dq.isEmpty()) {
                        String mid = decodeString(s.substring(j+1, i));
                        int dups = Integer.parseInt(s.substring(last, j));
                        for (int k = 0; k < dups; k++) sb.append(mid);
                        last = -1;
                    }
                }
            }
            return sb.toString();
        }
    }
    

Log in to reply
 

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