【题目】

将格式为 数[数[字母字母]数[字母]] 的字符串展开

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; 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].

 

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"

Example 4:

Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"

【思路】

DFS，本题中字符串一定是规范格式，不用考虑前后括号数。

讨论不同情况即可 2[a10[bc]]

【代码】

 

    public String decodeString(String s) {
        int num=0;
        StringBuilder sb=new StringBuilder();
        
        for(;i<s.length();i++){
            if(s.charAt(i)=='['){
                i++;
                String tmp=decodeString(s);
                //把[后余下字符串重新存入后调用，存在数字、字母两情况
                for(int k=0;k<num;k++){
                    sb.append(tmp);
                }
                num=0;//展开结束
            }

            else if(s.charAt(i)>='0'&&s.charAt(i)<='9'){
                num=10*num+s.charAt(i)-'0';//两位数以上，381[a]的情况
            }
            else if(s.charAt(i)==']'){
                return sb.toString();//括号结束，即此[]展开结束
            }
            else{
                sb.append(s.charAt(i));//[ab]的情况
            }
        }
           
        return sb.toString(); 
    }}