# 394 Decode String

input: 一串編碼過的字串，由數字(重複次數)和[string]表示要重複的字串

output: 解碼後的字串

3[a]2[bc] -> aaabcbc

3[a2[c]] -> accaccacc

Concept:

用一個StringBuilder來建構字串，

每次讀到一個數字，表示一組[ ]的開始。

將[ ]內的字串recursively丟進decodeString()。

終止條件：直到裡面沒有任何[ ]，就直接append裡面的字串到sb並回傳，

未達終止條件前，找到裡面的數字 n，把後面接的[ ]內的字串丟進decodeString()，

收到回傳的字串後，重複append n次到sb，再回傳。

Pseudocode:

String countString;
int count;
int index = 0;

StringBuilder sb
while index < s.length()
    if s.charAt(index) is number
        while(s.charAt(index) is not '[') 
            add to countString
            index++
        count = countString to integer
        countString = ""
        int ptr = 1;
        index++;//move from [ to next char
        while(ptr!=0){//explore if there's any bracket inside current bracket
            if (s.charAt(index) == '[') count ++;
            else if (s.charAt(index) == ']') count --;
            index++;
        }
        index--;//move from ] to previous char
        String str = decodeString(s.substring(str_begin, i))
        repeat current str count times, append to sb.
    else
        sb.append(s.charAt(index))

return sb;

實作時發現每組字串後面會多append一個 ]，

所以在內部沒有[]的純字串情況下，多一個判斷式排除]。

Code:

public class Solution {
    public String decodeString(String s) {

        String countString = "";
        int count = 0;
        int index = 0; //index
        if (s.length() == 0) return "";
        StringBuilder sb = new StringBuilder();
        while (index < s.length()){
            if (Character.isDigit(s.charAt(index))){
                while(s.charAt(index)!='['){
                    countString = countString + s.charAt(index);
                    index++;
                }
                count = Integer.parseInt(countString);
                countString = "";
                int ptr = 1;
                index++;//move from [ to next char
                int str_begin = index;
                //explore if there's any bracket inside current bracket, find corresponding bracket
                while(ptr!=0){
                    if (s.charAt(index) == '[') ptr++;
                    else if (s.charAt(index) == ']') ptr--;
                    index++;
                }
                index--;//move from ] to previous char
                //call decodeString for substring inside the brackets
                String str = decodeString(s.substring(str_begin, index));
                for(int i=0; i<count; i++){
                    sb.append(str);
                }
            }
            else{
                if(s.charAt(index)!=']')
                    sb.append(s.charAt(index));
                index++;
            }

        }
        return sb.toString();
    }


}