394. Decode String

// LeetCode URL: https://leetcode.com/problems/decode-string/

/**
 * Recursive One Pass solution
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: Depth of the recursion stack can maximum grow upto N/3.
 * StringBuilder can grow upto the size of the result.
 *
 * Total Space Complexity: O(N/3 + M) = O(N + M).
 *
 * N = Length of the input string. M = Length of StringBuilder.
 */
class Solution {
    public String decodeString(String s) {
        if (s == null) {
            return "";
        }
        if (s.length() < 4) {
            return new String(s);
        }

        return decodeStringHelper(s, new int[1]);
    }

    private String decodeStringHelper(String s, int[] idx) {
        StringBuilder sb = new StringBuilder();
        int num = 0;

        while (idx[0] < s.length() && s.charAt(idx[0]) != ']') {
            if (!Character.isDigit(s.charAt(idx[0]))) {
                sb.append(s.charAt(idx[0]));
                idx[0]++;
            } else {
                while (Character.isDigit(s.charAt(idx[0]))) {
                    num = num * 10 + s.charAt(idx[0]) - '0';
                    idx[0]++;
                }

                idx[0]++; // '['
                String tmp = decodeStringHelper(s, idx);
                idx[0]++; // ']'

                while (num > 0) {
                    sb.append(tmp);
                    num--;
                }
            }
        }

        return sb.toString();
    }
}