字符串解码

394. 字符串解码

题目描述

编码规则为：k[encoded_string], 即中括号前表示重复的次数，中括号里面的是重复的字符串

例子：

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

尝试

• 用栈的方式去解决问题
• 用递归的方式

递归解决

• 以3[a2[c]]为例子, 变量为s
• 遍历字符串s,
• 如果是数字, /\d/.test(s[i]), i++,
• 如果直接是字母,那直接往后扫, i++
• 遇到[进入递归
• 遇到]结束递归，同时返回[encode_string]中括号里面的内容, 同时返回当前index，即当前]在s[]中第几位
• 将第6步返回的值和第3步的重复次数，做个for循环就好了

代码实现

var decodeString = function(s) {
    let res = "";
    const sub = generate(s, 0);
    res += sub.sub;
    return res
}
// 3[a2[c]]
function generate(string, start) {
    let index = start;
    let temp = "";
    let tempNum = "";

    while(index < string.length) {
        const current = string[index];
        if(current == "[") {
            const sub = generate(string, index + 1 );
            let res = "";
            index = (sub.index)
            for(let i = 0 ; i < tempNum ; i++) {
                res += sub.sub
            }
            temp += res;
            tempNum = "";
        } else if(current == "]") {
            let res = temp;
            return {index: index + 1, sub: res}
        } else if(/\d/.test(current)) {
            tempNum += current
            index++;
         } else {
            temp += current
            index++
         }
    }
    return {index: index, sub: temp} 
}