摘要：利用棧我們可以存儲(chǔ)外圍層已持有的字符串以及應(yīng)當(dāng)展開的次數(shù)。用棧的思路來寫要求思路更加嚴(yán)謹(jǐn)，以免出現(xiàn)邏輯錯(cuò)誤。這里需要額外注意的是，如果當(dāng)前該括號(hào)外圍存在父元素，則我們應(yīng)當(dāng)將父元素的計(jì)數(shù)和已有字符串壓入棧中。

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 like 3a or 2[4].

Examples:

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

將一個(gè)字符串解碼，要求按照次數(shù)展開原字符串中的中括號(hào)。如3[a]2[bc]對(duì)應(yīng)的字符串就是aaabcbc，即a展開3次，bc展開2次。注意，源字符串中的括號(hào)是允許嵌套的，且展開的字符中不會(huì)包含任何數(shù)字。

其實(shí)遞歸的思路是很明顯的，一旦我們遇到一個(gè)左括號(hào)，我們就可以找到其對(duì)應(yīng)的右括號(hào)，然后對(duì)括號(hào)中的內(nèi)容遞歸的展開，再將返回結(jié)果給上層，根據(jù)上次的次數(shù)再次展開。
如3[a2[c]]=>3[acc]=>accaccacc。

遞歸這里需要注意的是如何找到當(dāng)前括號(hào)對(duì)應(yīng)的右括號(hào)。這里可以采用一個(gè)小技巧，即從當(dāng)前括號(hào)位置開始，每遇到一個(gè)左括號(hào)計(jì)數(shù)就+1，遇到一個(gè)右括號(hào)計(jì)數(shù)就-1，當(dāng)計(jì)數(shù)器第一次被減為0時(shí)，則該位置上的右括號(hào)就是我們所要找的對(duì)應(yīng)的右括號(hào)。

代碼如下：

    public String decodeString2(String s) {
        if (s.length() == 0)
            return "";

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= "0" && c <= "9") {
                // 解析次數(shù)
                int digitStart = i++;
                while (s.charAt(i) >= "0" && s.charAt(i) <= "9")
                    i++;
                int num = Integer.parseInt(s.substring(digitStart, i));

                // 找到對(duì)應(yīng)的右括號(hào)
                int strStart = i+1; // number must be followed by "["
                int count = 1; 
                i++;
                while (count != 0) {
                    if (s.charAt(i) == "[")
                        count++;
                    else if (s.charAt(i) == "]")
                        count--;
                    i++;
                }
                i--; 

                // 取子字符串
                String subStr = s.substring(strStart, i);

                // 將子字符串解碼
                String decodeStr = decodeString(subStr);

                // 將解碼的結(jié)果拼接到當(dāng)前的字符串后面
                for (int j = 0; j < num; j++) {
                    sb.append(decodeStr);
                }

            } else {
                // 添加首元素
                sb.append(c);
            }

        }

        return sb.toString();
    }

我們知道，有一些遞歸的思路是可以轉(zhuǎn)化為棧的，這里同樣如此。利用棧我們可以存儲(chǔ)外圍層已持有的字符串以及應(yīng)當(dāng)展開的次數(shù)。用棧的思路來寫要求思路更加嚴(yán)謹(jǐn)，以免出現(xiàn)邏輯錯(cuò)誤。首先，我們會(huì)用兩個(gè)指針lft，rgt分別來記錄數(shù)字的起始位置和結(jié)束位置。同時(shí)，rgt還作為我們遍歷整個(gè)字符串的指針。rgt的情形有如下幾種可能：

rgt指向[

rgt指向]

rgt指向數(shù)字

rgt指向字母

下面我們來逐個(gè)分析各種場(chǎng)景：

此時(shí)左括號(hào)的左側(cè)只會(huì)有一種情形，它的左邊一定是數(shù)字。
因此當(dāng)我們遇到左括號(hào)時(shí)，我們應(yīng)當(dāng)記錄左括號(hào)左邊的數(shù)字，并將lft指針移動(dòng)到左括號(hào)下一個(gè)位置。這里需要額外注意的是，如果當(dāng)前該括號(hào)外圍存在父元素，則我們應(yīng)當(dāng)將父元素的計(jì)數(shù)和已有字符串壓入棧中。可以將這個(gè)操作理解為上下文切換。

右括號(hào)意味著當(dāng)前的字符展開序列遍歷完畢，因此我們需要做以下幾件事情：

將lft和rgt之間的內(nèi)容append到當(dāng)前上下文的字符串中

根據(jù)展開次數(shù)展開當(dāng)前上下文的字符串

如果存在父元素，則從棧中彈出父元素，恢復(fù)父級(jí)上下文

將當(dāng)前上文得到的結(jié)果append到父元素的字符串中

我們需要將rgt指向的字母添加到當(dāng)前的上下文字符串中去。不要忘記將左指針移動(dòng)到當(dāng)前位置后面

數(shù)字將會(huì)在遇見[時(shí)提取出來，因此我們無需進(jìn)行任何處理

假如現(xiàn)在輸入的字符串為3[a2[c]]，我們有字符串棧s，計(jì)數(shù)棧c，指針lft，rgt，并用臨時(shí)變量tmp，number分別記錄當(dāng)前上下文中計(jì)數(shù)和字符串。運(yùn)行情況如下：

lft=0 rgt=0 : 不執(zhí)行任何操作
lft=0 rgt=1 : 解析當(dāng)前上下文應(yīng)當(dāng)展開的次數(shù) number=3, lft=2
lft=2 rgt=2 : 將當(dāng)前的字符添加到當(dāng)前的上下文中去，tmp="a" lft=3
lft=3 rgt=3 : 不做任何處理
lft=3 rgt=4 : 將父級(jí)上下文壓入棧中，并解析當(dāng)前上下文的展開次數(shù) s:["a"] c:[3] lft=5 tmp="" number=2
lft=5 rgt=5 : 將當(dāng)前的字符添加到當(dāng)前的上下文中去，tmp="c" lft=6
lft=6 rgt=6 : 展開當(dāng)前字符串，并恢復(fù)父級(jí)上下文, tmp="a"+"cc", number=3 s:[] c:[] lft=7
lft=7 rgt=7 : 展開當(dāng)前字符串，= 此時(shí)沒有父級(jí)上下文，因此無需恢復(fù)。tmp="accaccacc" number=0

代碼如下：

    public String decodeString(String s) {
        Stack count = new Stack<>();
        Stack letters = new Stack<>();
        int lft = 0, rgt = -1;
        int number = 0;
        StringBuilder result = null;
        while(++rgt < s.length()) {
            char c = s.charAt(rgt);
            if(c == "[") {
                if(result != null) {
                    count.push(number);
                    letters.push(result);
                }
                result = new StringBuilder();
                number = Integer.valueOf(s.substring(lft, rgt));
                lft = rgt+1;
            }else if(c == "]") {
                result.append(s.substring(lft, rgt));                    
                StringBuilder tmp = new StringBuilder(result);
                for(int i = 0 ; i

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~