原题

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

编码规则为: 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”.

解法

思想

DFS，只处理字符串中不包含括号的，遇到带括号的将其分解。

代码

class Solution {
    public String decodeString(String s) {
        return multify(1,s);
    }
    public String multify(int repeat,String s){
        StringBuilder sb = new StringBuilder();
        //字符串中不带括号
        if(s.indexOf('[') == -1){
            for(int i = 0;i<repeat;i++){
                sb.append(s);
            }
            return sb.toString();
        }else{
            //未匹配括号的个数
            int count = 0;
            //第一个数字出现的index
            int firstNumberIndex = 0;
            //第一个左括号出现的index
            int firstLeftIndex = 0;
            boolean firstNumberHasShown = false;
            for(int i = 0;i<s.length();i++){
                //如果是数字记录第一个数字出现的index
                if(s.charAt(i)>='0'&&s.charAt(i)<='9'){
                    if(firstNumberHasShown == false){  
                        firstNumberIndex = i;
                        firstNumberHasShown = true;
                    }
                }
                //如果是左括号记录第一个左括号出现的index
                else if(s.charAt(i) == '['){
                    if(count == 0)
                        firstLeftIndex = i;
                    count ++;
                }
                //如果是右括号则未匹配的左括号数量减一，如果全部匹配完则把repeat和substring递归处理。
                else if(s.charAt(i) == ']'){
                    count --;
                    if(count == 0) {
                        firstNumberHasShown = false;
                        int repeatNum = Integer.valueOf(s.substring(firstNumberIndex,firstLeftIndex));
                        String subString = s.substring(firstLeftIndex+1,i);
                        sb.append(multify(repeatNum,subString));
                    }   
                }
                else if(count==0){
                    sb.append(s.charAt(i));
                }
            }
        }
        return multify(repeat,sb.toString());
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode394-%e5%ad%97%e7%ac%a6%e4%b8%b2%e8%a7%a3%e7%a0%81/

leetcode394-字符串解码

原题

解法

思想

代码

相关推荐

发表回复