[LeetCode] Decode String 解碼字元串

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

The encoding rule is: <code>k[encoded_string]</code>, 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 like <code>3a</code> or <code>2[4]</code>.

Examples:

這道題讓我們把一個按一定規則編碼後的字元串解碼成其原來的模樣，編碼的方法很簡單，就是把重複的字元串放在一個中括号裡，把重複的次數放在中括号的前面，注意中括号裡面有可能會嵌套中括号，這題可以用遞歸和疊代兩種方法來解，我們首先來看遞歸的解法，我們把一個中括号中的所有内容看做一個整體，一次遞歸函數傳回一對中括号中解碼後的字元串。給定的編碼字元串實際上隻有四種字元，數字，字母，左中括号，和右中括号。那麼我們開始用一個變量i從0開始周遊到字元串的末尾，由于左中括号都是跟在數字後面，是以我們首先遇到的字元隻能是數字或者字母，如果是字母，我們直接存入結果中，如果是數字，我們循環讀入所有的數字，并正确轉換，那麼下一位非數字的字元一定是左中括号，我們指針右移跳過左中括号，對之後的内容調用遞歸函數求解，注意我們循環的停止條件是周遊到末尾和遇到右中括号，由于遞歸調用的函數傳回了子中括号裡解碼後的字元串，而我們之前把次數也已經求出來了，那麼循環添加到結果中即可，參見代碼如下：

解法一：

我們也可以用疊代的方法寫出來，當然需要用stack來輔助運算，我們用兩個stack，一個用來儲存個數，一個用來儲存字元串，我們周遊輸入字元串，如果遇到數字，我們更新計數變量cnt；如果遇到左中括号，我們把目前cnt壓入數字棧中，把目前t壓入字元串棧中；如果遇到右中括号時，我們取出數字棧中頂元素，存入變量k，然後給字元串棧的頂元素循環加上k個t字元串，然後取出頂元素存入字元串t中；如果遇到字母，我們直接加入字元串t中即可，參見代碼如下：

解法二：