###### tags: `Leetcode` `medium` `stack` `python` `c++`

# 394. Decode String

## [題目連結:]
Given an encoded string, return its 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; there are 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 will not be input like ```3a``` or ```2[4]```.

The test cases are generated so that the length of the output will never exceed ```10^5```.

**Example 1:**

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

**Example 2:**

Input: s = "3[a2[c]]"
Output: "accaccacc"

**Example 3:**

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

## 解題想法:
* 此題為對字串進行解碼，編碼方式為: 數字+[字串]=> 字串連續重複數字次
* 求最後解碼的字串

* 使用Stack
* init:
* cur_num='' :紀錄當前數字
* cur_str='' :紀錄當前字符
* for item in s:
* **Case1:** item=='['
* 將cur_num、cur_str存入stack
* 並將其重設為空字串''
* stack.append(cur_str)
* stack.append(cur_num)
* cur_num=cur_str=''
* **Case2:** item==']':
* 將數字、字符pop出來進行計算
* num=stack.pop()
* **pre_str**=stack.pop()
* **cur_str=pre_str+cur_str * num**
* **Case3:** item.isdigit() 是否為數字
* cur_num+=item
* 因為型式為char，直接累加即可，不用考慮個位十位進位問題
* **Case4:** 位字符
* cur_str+=item
* final return cur_str

* trace:

s = "3[a]2[bc]"
stack=[]
cur_num=''
cur_str=''

for item in s:

loop1: item='3'
cur_num='3'

loop2: item='['
stack=[ '', '3']
cur_num=''

loop3: item='a'
cur_str=a

loop4: item=']'
num='3'
pre_str=''
cur_str=''+a*3 =aaa
stack=[]

loop5: item='2'
cur_num='2'

loop6: item='['
stack=[ "aaa", '2']
cur_str=''
cur_num=''

loop7: item='b'
cur_str='b'

loop8: item='c'
cur_str='bc'

loop9: item=']'
num='2'
pre_str="aaa"
cur_str="aaa"+"bc"*2

return "aaabcbc"

## Python:

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        stack=[]
        cur_num='' #當前數字
        cur_str='' #當前字符
        for item in s:
            if item=='[':
                stack.append(cur_str)
                stack.append(cur_num)
                cur_num=''
                cur_str=''
            elif item==']':
                num=stack.pop()
                pre_str=stack.pop()
                cur_str=pre_str+cur_str*int(num)
            elif item.isdigit():
                cur_num+=item
            else:
                cur_str+=item
        return cur_str

result=Solution()
ans=result.decodeString(s = "3[a]2[bc]")
print(ans)

## C++:

class Solution {
public:
    string decodeString(string s) {
        stack<string> tmp;
        string cur_num="", cur_str="";
        for (auto item: s){
            if (item=='['){
                tmp.push(cur_str);
                tmp.push(cur_num);
                cur_str="";
                cur_num="";
            }
            else if (item==']'){
                string num=tmp.top(); tmp.pop();
                string pre_str=tmp.top(); tmp.pop();
                for (int i=0; i<stoi(num); i++){ // stoi: string to int
                    pre_str+=cur_str;
                }
                cur_str=pre_str;
            }
            else if (isdigit(item))
                cur_num+=item;
            else
                cur_str+=item;
        }
        return cur_str;
        
    }
};