394 Decode String

394. Decode String

1. Question

Given an encoded string, return it's decoded string.

The encoding rule is:k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like3aor2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

2. Implementation

(1) Stack

思路：这题和Basic Calculator很像，都是在scan输入字符串的过程中，当遇到特定的符号时，将之前处理的变量进行一些操作。Basic Calculator是进行四则运算，这里则是decode。所以对于这类问题，stack非常合适。但有一些不同的是，这里不仅要处理数字，还有string，所以我们用两个stack：num和letters 分别存放数字和已经decode的string。

(1) 当遇到数字时，处理方式和Basic Calculator一样，这里我们存放在count这个变量里，当遇到字母时，放在一个StringBuilder里，这里我们将这个StringBuilder命名为 res

(2) 当遇到'['时，说明有新的一部分需要decode，将之前得到count和res, 存放在不同的两个stack，并将两个变量的值清空

(3) 当遇到']'时，说明有一部分已经decode完成，从num中pop出数字，从letters中pop出之前已经decode的string，按照数字把当前获得的string加到已经解析的string的部分

class Solution {
    public String decodeString(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        int count = 0;
        Stack<Integer> num = new Stack<>();
        Stack<StringBuilder> letters = new Stack<>();
        StringBuilder res = new StringBuilder();
        StringBuilder curStr = null;

        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                count = 10 * count + c - '0';
            }
            else if (c == '[') {
                num.push(count);
                letters.push(res);
                count = 0;
                res = new StringBuilder();
            }
            else if (c == ']') {
                curStr = res;
                res = letters.pop();
                for (int i = num.pop(); i > 0; i--) {
                    res.append(curStr);
                }
            }
            else {
                res.append(c);
            }
        }
        return res.toString();
    }
}

(2) DFS

public class Solution {
    public String decodeString(String s) {
        int[] index = new int[1];
        return dfs(s, index);
    }

    public String dfs(String s, int[] index) {
        String res = "";
        int len = s.length();
        int count = 0;

        while (index[0] < len) {
            if (Character.isDigit(s.charAt(index[0]))) {
                count = 10 * count + s.charAt(index[0]) - '0';
            }
            else if (s.charAt(index[0]) == '[') {
                // Skip '['
                ++index[0];
                String nextStr = dfs(s, index);
                while (count > 0) {
                    res += nextStr;
                    --count;
                }
            }
            else if (s.charAt(index[0]) == ']') {
                return res;
            }
            else {
                res += s.charAt(index[0]);
            }
            ++index[0];
        }
        return res;
    }
}

3. Time & Space Complexity

Stack: 时间复杂度O(n), 空间复杂度O(n)

DFS: 时间复杂度O(n), 空间复杂度O(n)