题解 | #字符串解码#

字符串解码

http://www.nowcoder.com/practice/4e008fd863bb4681b54fb438bb859b92

题目：

给一个加密过的字符串解码，返回解码后的字符串。

加密方法是：k[c] ，表示中括号中的 c 字符串重复 k 次，例如 3[a] 解码结果是 aaa ，保证输入字符串符合规则。不会出现类似 3a , 3[3] 这样的输入。

方法一：双端队列

这道题我们首先会想到用栈解决，这里用双端队列更好，准备两个双端队列：multi_stack存储每次要重复的次数，因为要重复的次数可能大于10，所以，需要通过multi来存储计算重复次数k，用st来存储需要重复的字符c.
于是当遇到左括号时，说明这一轮的重复次数已经计算完毕，将multi进队列，res存储着左括号右边的字符，遇到第一个右括号后就可以取出multi_stack中的次数k将res做计算，得到内层括号中的字符后，将st中的字符出栈拼接与res拼接，得到的字符串为上一层括号需要重复的字符串.
以此类推，再继续出栈multi_stack中的数字，，计算重复字符串，再继续拼接....

alt

java
javascript

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String decodeString (String s) {
        // write code here
        int multi=0;//记录每次重复次数
        Deque<String>st=new LinkedList<>();
        Deque<Integer>multi_st=new LinkedList<>();
        char[]str=s.toCharArray();
        StringBuilder res=new StringBuilder();//保存结果
        for(int i=0;i<str.length;i++){
            char c=str[i];
            if(c>='0'&&c<='9')multi=multi*10+c-'0';//重复次数可能大于10，计算重复次数
            else if(c=='['){//遇到左括号，把需要这一轮的重复次数进栈，保存的结果字符串进栈
                multi_st.addLast(multi);
                st.addLast(res.toString());
                multi=0;//重复次数置0开始下一轮
                res=new StringBuilder();//结果字符串置空
            }
            else if(c==']'){//遇到右括号，把保存的重复次数出栈，用temp保存该轮重复字符串
                StringBuilder temp=new StringBuilder();
                int curr_multi=multi_st.removeLast();
                //System.out.print(curr_multi+" ");
                for(int j=0;j<curr_multi;j++){
                    temp.append(res);
                }
                res=new StringBuilder(st.removeLast()+temp);//计算完这一轮的重复字符串后将其拼接到栈中，初始化为结果字符串，结果字符串作为上对括号的重复子字符串
            }
            else res.append(c);
        }
        return res.toString();

    }
}

function decodeString( s ) {
    // write code here
    let st=[];
    let mulpti_st=[];
    let mulpti=0;
    let res='';
    for(const c of s){
        if(!isNaN(c))mulpti=mulpti*10+Number(c);
        else if(c=='['){
            st.push(res);
            mulpti_st.push(mulpti);
            res='';
            mulpti=0;
        }
        else if(c==']'){
            let temp='';
            let curr_mulpti=mulpti_st.pop();
            for(let i =0;i< curr_mulpti;i++){
                temp+=res;
            }
            res=st.pop()+temp;
        }else res+=c;
        
    }
    return res;
}
module.exports = {
    decodeString : decodeString
};

复杂度：

时间复杂度： $O (n)$ ,一次循环
空间复杂度： $O (n)$ ,额外为辅助栈开辟空间

方法二：递归

把字符串先放入队列，再对队列进行递归，每次队列都会移除元素，方便对括号内的字符进行递归，不用对右括号索引进行记录。
将队列元素出队的时候遇到左括号则开始递归遍历左括号右边的字符；递归的结束条件就是遇到右括号，这时把保存的字符串返回给上一层递归，对字符串进行重复次数的拼接。

alt

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String decodeString (String s) {
        // write code here
        Queue<Character>q=new LinkedList<>();
        for(int i=0;i<s.length();i++){
            q.add(s.charAt(i));//将字符存储在队列中方便递归
        }
        return decode(q);
    }
    String decode(Queue<Character>q){
        int num=0;
        StringBuilder res=new StringBuilder();
        while(!q.isEmpty()){
            char c=q.poll();
            if(c>='0'&&c<='9')num=num*10+c-'0';
            else if(c=='['){//遇到左括号开始递归，将左括号右边的数据进行递归
                String temp=decode(q);
                while(num>0){
                    res.append(temp);
                    num--;
                }
            }
            else if(c==']'){//递归结束条件返回res字符串
                return res.toString();
            }
            else{
                res.append(c);
            }
        }
        return res.toString();
    }
}