Decode String

NeetCode: Decode String · LeetCode: 394. Decode String · Difficulty: Medium

Given an encoded string, return its decoded form. The rule is k[encoded_string], meaning encoded_string is repeated exactly k times, where k is a positive integer. Brackets can be nested, and the input is always valid: plain text consists of lowercase letters, and digits only appear as repeat counts.

Example

Text

Input:  s = "3[a]2[bc]"        Output: "aaabcbc"
Input:  s = "3[a2[c]]"         Output: "accaccacc"
Input:  s = "2[abc]3[cd]ef"    Output: "abcabccdcdcdef"

Brute force: expand the innermost brackets, repeatedly

The first ] in the string always closes an innermost group, because nothing inside it is still open. Find it, find the [ that opens it (the last [ before it), read the digits immediately before that [, and replace k[inner] by inner repeated k times. Repeat until no ] is left. String.repeat(k) returns the string repeated k times. String is immutable, so every substring and + creates a new string.

Java

class Solution {
    public String decodeString(String s) {
        while (s.indexOf(']') >= 0) {
            int close = s.indexOf(']');
            int open = s.lastIndexOf('[', close);
            int start = open;
            while (start > 0 && Character.isDigit(s.charAt(start - 1))) {
                start--;
            }
            int k = Integer.parseInt(s.substring(start, open));
            String inner = s.substring(open + 1, close).repeat(k);
            s = s.substring(0, start) + inner + s.substring(close + 1);
        }
        return s;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.decodeString("3[a]2[bc]"));
        System.out.println(sol.decodeString("3[a2[c]]"));
        System.out.println(sol.decodeString("2[abc]3[cd]ef"));
        System.out.println(sol.decodeString("10[a]"));
        System.out.println("[" + sol.decodeString("") + "]");
    }
}

Output

aaabcbc
accaccacc
abcabccdcdcdef
aaaaaaaaaa
[]

Time: each pass rebuilds the whole string, so it is O(g · L) for g bracket groups and a working string of length up to L (the decoded length), which is quadratic in the worst case. Space: O(L).

Optimal: a stack of (text so far, repeat count)

Scan once, keeping the text being built (cur, a StringBuilder) and the number being read (num). Digits extend num. On [ a group begins: push cur and num onto two parallel ArrayDeque stacks and start a fresh cur. On ] the group is finished: pop the previous text prev and the count k, append cur to prev k times, and continue with prev as cur. Letters are appended to cur. Nesting works because the stacks remember what surrounded each open bracket. The digit test uses c >= '0' && c <= '9' and c - '0', because char arithmetic gives the digit value as an int.

Java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public String decodeString(String s) {
        Deque<StringBuilder> texts = new ArrayDeque<>(); // text before each open bracket
        Deque<Integer> counts = new ArrayDeque<>();      // repeat count of each open bracket
        StringBuilder cur = new StringBuilder();
        int num = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                num = num * 10 + (c - '0');
            } else if (c == '[') {
                texts.push(cur);
                counts.push(num);
                cur = new StringBuilder();
                num = 0;
            } else if (c == ']') {
                StringBuilder prev = texts.pop();
                int k = counts.pop();
                for (int r = 0; r < k; r++) {
                    prev.append(cur);
                }
                cur = prev;
            } else {
                cur.append(c);
            }
        }
        return cur.toString();
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.decodeString("3[a]2[bc]"));
        System.out.println(sol.decodeString("3[a2[c]]"));
        System.out.println(sol.decodeString("2[abc]3[cd]ef"));
        System.out.println(sol.decodeString("10[a]"));
        System.out.println("[" + sol.decodeString("") + "]");
    }
}

Output

aaabcbc
accaccacc
abcabccdcdcdef
aaaaaaaaaa
[]

Time: O(L) where L is the length of the decoded output (each output character is written a constant number of times per nesting level it passes through, so deep nesting can add a factor of the depth). Space: O(L).