[数据结构与算法]第3题 力扣LeetCode 热题 HOT 100(394. 字符串解码)

第3题 力扣LeetCode 热题 HOT 100(394. 字符串解码)

题目

394. 字符串解码

难度中等841收藏分享切换为英文接收动态反馈

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

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

题解

解题思路，设置变量result为返回的结果。

子问题分解，分解规则，以匹配的中括号为一个子字符串，调用字符串解码函数，返回子字符串，把子字符串添加k次至结果中。

遇到 数字 则计算连续字符中数字的值（k），然后进行梳子后的中括号匹配，得出字符串的左右区间，获得子字符串，调用字符串编码函数，返回的值添加k次至result中。

遇到 字符 ，则直接添加至result 中。

以实例2为例

s = “3[a2[c]]”

第一个为数字3 ，进行数字后的中括号匹配得到，子字符串为a2[c] ，调用对子字符串字符串解码函数，往result中添加3次

子字符串 a2[c] 子子字符串 c，

decodeString(‘a2[c]’)返回acc ,其中还会调用一次decodeString(‘c’) 返回c。

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function(s) {
  // console.log(s)
  let k = 0;
  let result = '' ;
  let left, right;
  let leftNum, rightNum;
  for(let i = 0 ; i<s.length; i++) {
      let aChar = s[i];
      if(aChar<='9' && aChar>='0'){
        let value =0;  
        while(s[i]<='9' &&s[i]>='0' ){
            value = value*10+Number.parseInt(s[i]);
            i++;
         }
         i--;
         aChar = value;
        //  console.log(aChar)
          left = i+2;
          leftNum = 1;
          let addStr = ''
          for(let j = i+2; j<s.length; j++){
              if(s[j]=='[') leftNum++;
              else if(s[j]==']') leftNum--;
              
              if(leftNum==0) {
                i = j;
                addStr = decodeString(s.slice(left, j));
                break;
              }
          }

          for(let j = 0; j< Number.parseInt(aChar); j++){
            result = result+addStr;
          }
         
      }else{
          result = result+ aChar;
      }
  }
  
  return result ;
};