LeetCode 394: DecodeString (Java)

ccj659 發(fā)布于2019-08-14 15:50 / 2180人閱讀

摘要：思路非常清晰，但是實現(xiàn)起來并不簡單。得注意細節(jié)及其處理方式，比如數(shù)字可能出現(xiàn)兩位及以上并列關(guān)系和包含關(guān)系如何巧妙區(qū)分。另外發(fā)現(xiàn)大循環(huán)用而不是可能更方便一些。

解碼題。
編碼規(guī)則直接看例子(編碼后字符串->原字符串)：
2[b] -> bb
3[a2[c]] -> 3[acc] -> accaccacc
2[a2[b]ef]xy ->2[abbef]xy->abbefabbefxy

根據(jù)上面的結(jié)構(gòu)我們很容易想到用深搜算法：

先將"]" 之前的信息（要重復的部分及重復次數(shù)）壓到stack里，等到了"]"再一個一個推出還原。思路非常清晰，但是實現(xiàn)起來并不簡單。得注意細節(jié)及其處理方式，比如數(shù)字可能出現(xiàn)兩位及以上; 并列關(guān)系［］,［］和包含關(guān)系［［］］如何巧妙區(qū)分。另外發(fā)現(xiàn)大循環(huán)用while而不是for可能更方便一些。

下面是我在leetcode論壇上找到的比較好看的代碼（44%）：

public static String decodeString(String s) {
    Stack count = new Stack<>();
    Stack result = new Stack<>();//用Stack處理包含關(guān)系

    result.push("");
    int i = 0;

    while(i= "0" && a <= "9"){
            int p1 = i;
            while(Character.isDigit(s.charAt(i+1))) i++;
            count.push(Integer.parseInt(s.substring(p1,i+1)));
        } else if (a == "[") {
            result.push("");//用初始化空字符串處理并列關(guān)系
        } else if(a == "]") {
            String temp = new String(result.pop());
            StringBuilder sb = new StringBuilder();
            int nloop = count.pop();
            for(int j = 0; j < nloop;j++)
                sb.append(temp);
            result.push(result.pop()+sb.toString());
        } else {
            result.push(result.pop()+a);
        }
        i++;
    }
    return result.pop();
}

當然也可以用遞歸算法，但我感覺比較難想，這種算法比較直接，面試的時候想到比較實際。

Ref：Java short and easy-understanding solution using stack