394. Decode String

two stack

time: O(n)
space: O(s1+s2), stack space

use this

class Solution {
    public String decodeString(String s) {
        Deque<String> strStack = new ArrayDeque<>();
        Deque<Integer> numStack = new ArrayDeque<>();
        StringBuilder cur = new StringBuilder();
        
        for (int i = 0; i < s.length(); i++) {
            if (Character.isDigit(s.charAt(i))) {
                int i0 = i;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    i++;
                }
                int num = Integer.valueOf(s.substring(i0, i));
                numStack.push(num);
                strStack.push(cur.toString());
                cur = new StringBuilder();
                
            } else if (s.charAt(i) == ']') {
                
                int repeat = numStack.pop();
                String temp = cur.toString();
                for (int j = 0; j < repeat-1; j++) {
                    cur.append(temp);
                }
                cur = new StringBuilder(strStack.pop() + cur);
                
            } else if (Character.isLetter(s.charAt(i))) {
                cur.append(s.charAt(i));
            }
        }
        return cur.toString();
    }
}

/*
number: add number to number, cur str stack
1. number add to num stack, 因為 num 後面就是 [, so add cur to str stack too, clear cur
2. char: add to cur
3. 遇到 ], num 出戰, str 出站, num*str => set to cur 

     aaa 
3    ""
num. str

cur aaa -> ""

     
2    
num. str

cur aaabcbc => ans
*/

/*
"3[a2[c]]"

countStack: 3  ⇒ 2

resStack: "" ⇒ a

res ""  ⇒ a ⇒ "" c

meets ]

sb(a) + cc ⇒ res = acc

meets ]

countStack: 3

resStack: ""

res acc

sb("") + 3*acc

res = accaccacc

1. number ⇒ push countStack ⇒ number push

 2. '[' ⇒ push resStack ⇒ when '[', push res into it

1. char: add char 

1. ']' ⇒ pop

time: O(n)
space: O(s1+s2), stack space
*/
class Solution {
    public String decodeString(String s) {
        Deque<String> resStack = new ArrayDeque<>();
        Deque<Integer> numStack = new ArrayDeque<>();
        int i = 0;
        StringBuilder res = new StringBuilder();
        while (i < s.length()) {
            if (Character.isDigit(s.charAt(i))) {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num = num*10 + (s.charAt(i) - '0');
                    i++; // 最後會到下一位, 也就是多加了一次
                }
                numStack.push(num);
                i--; // 外層有個i++, 所這要 i--
            } else if (s.charAt(i) == '[') {
                resStack.push(res.toString());
                res = new StringBuilder();
                
            } else if (s.charAt(i) == ']') {
                StringBuilder temp = new StringBuilder(resStack.pop());
                int times = numStack.pop();
                for (int j = 0; j < times; j++) {
                    temp.append(res);
                }
                res = temp;
            } else {
                res.append(s.charAt(i));
            }
            i++;
        }
        return res.toString();
    }
}




/*
2 stack

d3[a]2[bc]d



3
numStack



when [, push to resStack
resstack



res+=letter


res = d

3
numStack

[

res = ""

d         3 
resstack  numStack


res = "a"

d         3 
resstack  numStack

]
res = "a"

d         3 
resstack  numStack


d3[a]2[bc]d

res = bc
daaa          2
resstack  numStack

res = daaabcbcd


*/

one stack

class Solution {
    public String decodeString(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ']') {
                
                List<Character> list = new ArrayList<>();
                while (stack.peek() != '[') {
                    list.add(stack.pop());
                }
                stack.pop(); // [
                int base = 1;
                int k = 0;
                while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
                    k += (stack.pop() - '0')*base;
                    base *= 10;
                }
                while (k != 0) {
                    for (int j = list.size()-1; j >= 0; j--) {
                        stack.push(list.get(j));
                    }
                    k--;
                }
                
            } else {
                stack.push(s.charAt(i));
            }
        }
        StringBuilder res = new StringBuilder();
        while(!stack.isEmpty()) {
            res.append(stack.pop());
        }
        return res.reverse().toString();
    }
}

/*
3[a2[c]]

c
[
2
a
[
3
*/

recursion

T: O(k*n), k is call dfs times, n is String length

S: O(n)

class Solution {

    public String decodeString(String s) {
        return dfs(s, 0)[0];
    }
    private String[] dfs(String s, int i) {
        StringBuilder res = new StringBuilder();
        
        int num = 0;
        while(i < s.length()) {
            if(Character.isDigit(s.charAt(i))) { 
                num = num * 10 + (s.charAt(i) - '0'); 
            } else if(s.charAt(i) == '[') { // when [, call dfs(s, i+1) get str in [ str ]
                
                String[] tmp = dfs(s, i + 1);
                i = Integer.parseInt(tmp[0]);
                
                for (int j = 0; j < num; j++) { // multi str, num needs set back to 0
                    res.append(tmp[1]);
                }
                num = 0;
            } else if(s.charAt(i) == ']') { // when end, return String
                return new String[] { String.valueOf(i), res.toString() };
                
            } else { // letter, add
                res.append(s.charAt(i));
            }
            i++;
        }
        return new String[] { res.toString() };
    }
}

/*
d3[a2[c]]d
    /
   a2[c]
   /
   c
   
   so when back, we can deal with number and decoded String
    => 2c => cc
    => acc
    => 3acc
    => daccaccaccd
*/

or i as global variable

class Solution {
    int i = 0;
    public String decodeString(String s) {
        return dfs(s);
    }
    private String dfs(String s) {
        StringBuilder res = new StringBuilder();
        
        int num = 0;
        while(i < s.length()) {
            if(Character.isDigit(s.charAt(i))) { 
                num = num * 10 + (s.charAt(i) - '0'); 
            } else if(s.charAt(i) == '[') { // when [, call dfs(s, i+1) get str in [ str ]
                i++;
                String tmp = dfs(s);                
                for (int j = 0; j < num; j++) { // multi str, num needs set back to 0
                    res.append(tmp);
                }
                num = 0;
            } else if(s.charAt(i) == ']') { // when end, return String
                return res.toString();
                
            } else { // letter, add
                res.append(s.charAt(i));
            }
            i++;
        }
        return res.toString();
    }
}