day4.[栈]394. 字符串解码

394. 字符串解码

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

编码规则为: 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) {
  let stack = [], count = 0, res = ''
  for(let i = 0; i < s.length; i ++) {
    let cur = s[i];
    if (/\d/.test(cur)) {
      count += cur;
    } else if (cur === '[') {
      stack.push([res, count])
      res = ''
      count = 0
    } else if (cur === ']') {
      let [_res, i] = stack.pop()
      res = _res + res.repeat(i)
    } else {
      res += cur;
    }
  }
  return res;
};

递归

var decodeString = function(s) {
  let [res] = dfs(s, 0);
  return res;
};

function dfs(s, i) {
  let res = '', count = '';
  while(i < s.length) {
    let cur = s[i]
    if (cur >= 0 && cur <= 9) {
      count += cur;
    } else if(cur == '['){
      let [tmp, idx] = dfs(s, i+1);
      i = idx;
      res += tmp.repeat(count);
      count = ''
    } else if(cur == ']'){
      break;
    } else {
      res += cur;
    }
    i++;
  }
  return [res, i];
}

复杂度分析

时间复杂度 #card=math&code=O%28N%29)

空间复杂度 #card=math&code=O%28N%29)