解码字符串 - Javascript

Question

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

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

编码规则为：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

此函数遍历字符串一次，这意味着它可能比正则表达式更快。

let string = "abc3[cd]xyz"

// this function returns true or false, depending on if the given string is a digit
const isNumber = c => (c >= '0' && c <= '9')

var decode = string => {
  let result = ""
  // the main loop
  // its faster to store 'len' than it is reuse 'string.length' every iteration
  for (let i=0,len=string.length; i<len; i++) {
    
    let character = string[i];
    
    // if the current character is a number, we know we need to decrypt the next chunk
    if (isNumber(character)) {
      let repeat_int = "";
      let repeat_string = "";
      
      // we keep looping through, adding each digit of the number to 'repeat_int'
      while (character !== "[") {
        repeat_int += character;
        i++;
        character = string[i];
      }
      
      // we need to jump ahead one extra character to avoid including "[" in the string
      i++;
      character = string[i];
      
      // we keep looping through, adding each character of the string to 'repeat_string'
      while (character !== "]") {
        repeat_string += character;
        i++;
        character = string[i];
      }
      
      // we repeat 'repeat_string' by 'repeat_int' times, and add it to the result
      result += repeat_string.repeat(repeat_int);


    // if the current character is a letter, we can simply add it to the result
    } else {
      result += character;
    }
  }
  return result;
}

Answer 2

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

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"

如果你想simplify/update/explore这个表达式，在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的右上面板已经解释过可能会逐步消耗一些示例输入字符串并执行匹配过程。

正则表达式电路

jex.im 可视化正则表达式：

Answer 3

This answer有创意，很好；我们也可以使用堆栈来解决这个问题。

这将被接受：

const decodeString = s => {
    const stack = [];
    for (const char of s) {
        if (char !== "]") {
            stack.push(char);
            continue;
        }

        let currChar = stack.pop();
        let decoded = '';
        while (currChar !== '[') {
            decoded = currChar.concat(decoded);
            currChar = stack.pop();
        }

        let num = '';
        currChar = stack.pop();

        while (!Number.isNaN(Number(currChar))) {
            num = currChar.concat(num);
            currChar = stack.pop();
        }

        stack.push(currChar);
        stack.push(decoded.repeat(Number(num)));
    }

    return stack.join('');
};

console.log(decodeString("3[a]2[bc]"))
console.log(decodeString("3[a2[c]]"))
console.log(decodeString("2[abc]3[cd]ef"))
console.log(decodeString("abc3[cd]xyz"))

在Python中，我们将类似地使用一个列表，它与Java脚本的数组非常相似：

class Solution:
    def decodeString(self, base_string):
        stack = []
        decoded = ''
        full_num = 0

        for char in base_string:
            if char == '[':
                stack.append(decoded)
                stack.append(full_num)
                decoded, full_num = '', 0
            elif char == ']':
                curr_digit, curr_char = stack.pop(), stack.pop()
                decoded = curr_char + curr_digit * decoded
            elif char.isdigit():
                full_num *= 10
                full_num += int(char)
            else:
                decoded += char

        return decoded

在 Java 中，我们会使用两个堆栈：

class Solution {
    public String decodeString(String string) {
        String decoded = "";
        Stack<Integer> numberStack = new Stack<>();
        Stack<String> decodedStack = new Stack<>();
        int count = 0;

        while (count < string.length()) {
            if (Character.isDigit(string.charAt(count))) {
                int fullNum = 0;

                while (Character.isDigit(string.charAt(count))) {
                    fullNum = 10 * fullNum + (string.charAt(count) - '0');
                    count++;
                }

                numberStack.push(fullNum);

            } else if (string.charAt(count) == '[') {
                decodedStack.push(decoded);
                decoded = "";
                count++;

            } else if (string.charAt(count) == ']') {
                StringBuilder temp = new StringBuilder(decodedStack.pop());
                int repeatTimes = numberStack.pop();

                for (int iter = 0; iter < repeatTimes; iter++)
                    temp.append(decoded);

                decoded = temp.toString();
                count++;

            } else
                decoded += string.charAt(count++);
        }

        return decoded;
    }
}

参考资料

有关其他详细信息，您可以在其中查看 Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2}。

解码字符串 - Javascript

Decode String - Javascript

javascript

depth-first-search

正则表达式电路

参考资料