字符串解码

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例:

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

在此题中可能出现括号嵌套的情况，比如 3[a2[c]]，这种情况下我们先转化为2[abcbc]，再转化成abcbcabcbc。我们可以使用栈或递归来实现。使用栈的具体做法是：

1. 如果当前字符为数字，则取出一个数字（连续的多个数位）并进栈。
2. 如果当前字符为字母或左括号，直接进栈。
3. 如果当前字符为右括号，开始出栈，直到出现左括号，此时栈顶元素为已经出栈的字符串重复出现的次数。

重复以上操作，直到遍历到字符串末尾。

class Solution {
    //访问字符的下标
    int ptr;

    public String decodeString(String s) {
        LinkedList<String> stack = new LinkedList<>();
        ptr = 0;

        while(ptr < s.length()){
            char cur = s.charAt(ptr);
            if(Character.isDigit(cur)){
                //获取数字并将字符串进栈
                String digits = getDigits(s);
                stack.addLast(digits);
            }else if((Character.isLetter(cur) || cur == '[')){
                //获取一个字母并进栈
                stack.addLast(String.valueOf(s.charAt(ptr++)));
            }else{
                //跳过右括号
                ++ptr;
                LinkedList<String> sub = new LinkedList<>();
                //将栈内字符串保存，直到遇到左括号
                while(! "[".equals(stack.peekLast())){
                    sub.addLast(stack.removeLast());
                }
                //将字符串顺序转换回来
                Collections.reverse(sub);

                //左括号出栈
                stack.removeLast();
                //此时栈顶元素为括号内字符串重复的次数，将字符串解析为数字
                int repTime = Integer.parseInt(stack.removeLast());
                //生成字符串
                StringBuffer t = new StringBuffer();
                String o = getString(sub);
                while(repTime-- > 0){
                    t.append(o);
                }
                //将字符串添加到栈顶
                stack.addLast(t.toString());
            }
        }

        return getString(stack);
    }

    private String getDigits(String s){
        //获取数字
        StringBuffer sb = new StringBuffer();
        while(Character.isDigit(s.charAt(ptr))){
            sb.append(s.charAt(ptr++));
        }
        return sb.toString();
    }

    private String getString(LinkedList<String> v){
        //整合结果
        StringBuffer sb = new StringBuffer();
        for(String s : v){
            sb.append(s);
        }
        return sb.toString();
    }
}

渐进时间复杂度为 O(S)，渐进空间复杂度为 O(S)。

我们还可以使用递归来完成此题。使用递归的具体做法是：

1. 如果当前位置为数字位，那么后面一定包含一个用方括号表示的字符串k[...]。

   • 我们可以先解析数字，然后递归解析后面的内容，遇到对应的右括号则可以根据解析的数字x 和字符串 s’ 构造一个新的字符串 x * s’。
   • 在解析完一个k[...]后，再次调用递归函数，解析右括号右边的内容。

2. 如果当前位置是字母位，直接解析当前字母，然后递归向下解析这个字母后面的内容。

class Solution {
    int ptr;
    String src;

    public String decodeString(String s) {
        src = s;
        ptr = 0;
        return getString();
    }

    private String getString(){
        //结束处理
        if(ptr == src.length() || src.charAt(ptr) == ']'){
            return "";
        }
        char cur = src.charAt(ptr);
        int repTime = 1;
        String ret="";
		
        if(Character.isDigit(cur)){//当前位置是数字
            //解析Digit
            repTime = getDigits();
            //过滤左括号
            ++ptr;
            //解析String
            String str = getString();
            //过滤右括号
            ++ptr;

            //构造字符串
            while(repTime-- > 0){
                ret += str;
            }
        }else if(Character.isLetter(cur)){//当前位置是字母
            ret = String.valueOf(src.charAt(ptr++));
        }
        //再次调用递归函数，解析右括号右边的内容
        return ret + getString();
    }
	//从字符串中解析数字
    private int getDigits(){
        int ret = 0;
        while(ptr < src.length() && Character.isDigit(src.charAt(ptr))){
            ret = ret * 10 + src.charAt(ptr++) - '0';
        }
        return ret;
    }
}

渐进时间复杂度为 O(S)，渐进空间复杂度为 O(S)。