解码字符串 - Javascript

Question

我正在尝试在 javascript 中实现解码字符串算法。

问题：给定一个编码字符串，返回它的解码字符串。

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

您可以假设输入字符串始终有效；没有多余的空格，方括号格式正确等。

此外，您可以假设原始数据不包含任何数字，并且数字仅用于那些重复数字 k。例如，不会有像 3a 或 2[4] 这样的输入。

示例 1：

输入：s = "3[a]2[bc]" 输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]" 输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef" 输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz" 输出："abccdcdcdxyz"

我的尝试：

var decodeString = function(s) {
    if(!s || s.length === 0)    return "";
    
    let map = {
        '0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6,
        '7': 7, '8': 8, '9': 9
    };
    let res = "";
    
    const dfs = (str) => {
        //let res = "";
        const arr = str.split("");
        for(let i=0; i<arr.length; i++) {
            if(arr[i] === '[') {
                // call dfs
                const close = getClosePos(i, arr);
                dfs(arr.splice(i+1,close-(i+1)).join(""));
            } else if(map[arr[i]] !== undefined) {
                // repet N next letters
                let k = map[arr[i]];
                while(k > 0) {
                    res += dfs(arr.splice(i+1,arr.length).join(""));
                    k--;
                }
            } else if(arr[i] !== ']') {
                res += arr[i];
            }
        }
        //return res;
    }
    dfs(s);
    
    return res;
};

const getClosePos = (i, arr) => {
    for(let j=i; j<arr.length; j++) {
        if(arr[j] === ']')
            return j;
    }
    return 0;
}

我的输出是： "undefinedundefinedundefined"

谢谢

Answer 1

您可以用正则表达式替换字符串并获得想要的嵌套替换，直到没有更多字符串可供替换。

const decodeString = string => {
let repeat
do {
    repeat = false;
    string = string.replace(/(\d+)\[([^\[\]]+)\]/g, (_, c, v) => {
        repeat = true;
        return v.repeat(c);
    });
} while (repeat);
return string;
}

console.log(decodeString("3[a]2[bc]")); // "aaabcbc"
console.log(decodeString("3[a2[c]]")); // "accaccacc"
console.log(decodeString("2[abc]3[cd]ef")); // "abcabccdcdcdef"
console.log(decodeString("abc3[cd]xyz")); // "abccdcdcdxyz"

If you wish to simplify/update/explore the expression, it's been explained on the top right panel of regex101.com. You can watch the matching steps or modify them in this debugger link, if you'd be interested. The debugger demonstrates that how a RegEx engine might step by step consume some sample input strings and would perform the matching process.

RegEx Circuit

jex.im visualizes regular expressions: