394. Decode String - jiejackyzhang/leetcode-note GitHub Wiki

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".

##Approach 1: Stack 解题思路为two stacks，一个记录次数，一个记录pattern。 遇到数字，把次数存在一个stack中。 遇到'['，把之前的string保存起来，开始记录一个新的pattern； 遇到']'，按次数输出n次pattern，然后连接上之前的string，成为一个新的string。 注意点是次数是1的时候，是没有数字的，直接将相应character往string上加。

public class Solution {
    public String decodeString(String s) {
        if(s == null || s.length() == 0) return "";
        
        Stack<Integer> times = new Stack<Integer>();
        Stack<String> stack = new Stack<String>();
        String cur = "";
        int len = s.length();
        int i = 0;
         while (i < len) {
             char c = s.charAt(i);
             if(Character.isDigit(c)) {
                 int digitBegin = i;
                 while(s.charAt(i) != '[') i++;
                 int num = Integer.valueOf(s.substring(digitBegin, i));
                 times.push(num);
             } else {
                 if(c == '[') {
                     stack.push(cur); // save previous string
                     cur = "";
                 } else if(c == ']') {
                     StringBuilder sb = new StringBuilder();
                     int n = times.pop();
                     while(n-- > 0) {
                         sb.append(cur);
                     }
                     sb.insert(0, stack.pop()); // concatenate with previous string
                     cur = sb.toString();
                 } else {
                     cur += c;
                 }
                 i++;
             }
         }
         return cur;
    }
}

##Approach 2: DFS

1. 遇到'['，则递归调用dfs，获取[]内的string，并重复num次，加在之前的string后；
2. 遇到']'，则将当前string返回，即该[]内的string已经完成。

注意index i需要设置为全局变量，这样在递归调用dfs后，i会在递归之后的位置上。

public class Solution {
    
    private int i = 0;
    
    public String decodeString(String s) {
        if(s == null || s.length() == 0) return "";
        return dfs(s, 0);
    }
    
    private String dfs(String s, int idx) {
        if(idx >= s.length()) return "";
        StringBuilder numStr = new StringBuilder();
        StringBuilder letterStr = new StringBuilder();
        for(i = idx; i < s.length(); i++) {
            char c = s.charAt(i);
            if(Character.isDigit(c)) numStr.append(c);
            if(Character.isLetter(c)) letterStr.append(c);
            if(c == '[') {
                String str = dfs(s, i+1);
                for(int j = 0; j < Integer.valueOf(numStr.toString()); j++) {
                    letterStr.append(str);
                }
                numStr.delete(0, numStr.length());
            } else if(c == ']') {
                return letterStr.toString();
            }
        }
        return letterStr.toString();
    }
}
⚠️ **GitHub.com Fallback** ⚠️