[路飞]_leetcode-394-字符串解码

简介: leetcode-394-字符串解码

网络异常,图片无法展示
|


[题目地址][B站地址]


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


编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。


你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。


此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a2[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"
复制代码


递归解题


解题思路


  1. 首先特判,如果输入字符串中没有中括号,则当前字符不需要解码,直接返回(即递归的终止条件)。
  2. 初始化 num 记录 k 值,stack 记录左括号下标, res 记录结果字符串。
  3. 遍历输入字符串,如果当前字符为左括号,将其下标入栈。
  4. 如果栈为空,当前字符为数字,组装 num,当前字符为非数字,将字符拼接到结果字符串后。
  5. 如果当前字符为右括号,则将栈顶元素弹出。如果弹栈后栈为空,则说明找到了一组最外层括号,截取中间部分字符,并重复对应 num 次,利用 decodeString 函数递归处理,并将处理后的结果拼接到结果字符串后。
  6. 如此遍历完输入字符串,res 中保存的就是解码后的字符串。


动画演示


网络异常,图片无法展示
|


代码实现


var decodeString = function(s) {
  // 如果当前字符串中没有中括号,不需要处理,直接返回
  if(s.indexOf('[')===-1) return s;
  // 初始化num,stack,res
  let num = 0,stack = [],res = '';
  // 遍历输入字符串
  for(let i = 0;i<s.length;i++){
    // 如果当前是左括号,将对应下标入栈
    if(s[i]==='['){
      stack.push(i);
      continue;
    }
    // 如果栈为空
    if(stack.length===0){
      // 如果是数字,组装 num
      if(!isNaN(s[i])){
        num = num*10+s[i]*1
      }else{
        // 如果是普通字符,拼接到结果字符串后
        res += s[i]
      }
      continue;
    }
    // 如果当前为右括号,将栈顶左括号弹出
    if(s[i]===']'){
      const start = stack.pop();
      // 如果栈为空,说明此时找到的是一组最外层的括号
      if(stack.length===0){
        // 截取括号中间部分并 repeat num 次,将结果递归处理,并将返回值拼接到结果字符串后
        res += decodeString(s.substring(start+1,i).repeat(num))
        // 重置num
        num = 0;
      }
    }
  }
  // 返回结果字符串
  return res;
};
复制代码


迭代解题


解题思路


  1. 初始化栈为空。
  2. 遍历输入字符串,如果当前字符为数字,获取对应数字并入栈。
  3. 如果当前字符为右括号,将栈顶字符弹出,组成字符串,直到遇到与之对应的左括号。此时,字符串中保存的就是括号中间部分,再将栈顶元素弹出,此时栈顶元素就是该部分编码字符对应的 k 值,将字符串重复 k 次,并将结果再次入栈。
  4. 其他字符直接入栈。
  5. 最后将栈中的字符串拼接为一个字符串,就是解码后的字符串。


动画演示


网络异常,图片无法展示
|


代码实现


var decodeString = function(s) {
  // 获取输入字符串长度并初始化栈
  const len = s.length,stack = [];
  // 遍历输入字符串
  for(let i = 0;i<len;i++){
    // 如果当前字符是数字
    if(!isNaN(s[i])){
      // 获取完整数字
      let num = s[i];
      for(let j = i+1;j<len;j++){
        if(!isNaN(s[j])){
          num = num*10+s[j]*1
        }else{
          // 将获取到的数字入栈
          stack.push(num);
          i = j-1;
          break;
        }
      }
    }else if(s[i]===']'){
      // 如果当前为右括号,将栈中字符弹出,直到遇到与之对应的左括号
      let str = '';
      while(stack.length){
        const code = stack.pop();
        if(code==='['){
          // 此时栈顶元素是该部分字符对应的 k 值,将其弹出,并将字符 repeat k 次并入栈
          stack.push(str.repeat(stack.pop()))
          break;
        }else{
          // 组装括号中间字符
          str = code+str;
        }
      }
    }else{
      // 其他情况,直接将字符入栈
      stack.push(s[i])
    }
  }
  // 最后栈中字符串拼接之后的结果,即为解码后的字符串
  return stack.join('')
};
复制代码


至此我们就完成了 leetcode-394-字符串解码


如有任何问题或建议,欢迎留言讨论!

相关文章
|
16天前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
30 1
|
30天前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
23 9
|
30天前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
15 0
|
30天前
【LeetCode 22】459.重复的子字符串
【LeetCode 22】459.重复的子字符串
27 0
|
30天前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
17 0
|
30天前
【LeetCode 19】541.反转字符串II
【LeetCode 19】541.反转字符串II
19 0
|
30天前
【LeetCode 18】6.2.反转字符串
【LeetCode 18】6.2.反转字符串
14 0
|
3月前
|
存储 算法
LeetCode第43题字符串相乘
LeetCode第43题"字符串相乘"的解题方法,通过使用数组存储乘积并处理进位,避免了字符串转换数字的复杂性,提高了算法效率。
LeetCode第43题字符串相乘
|
3月前
|
算法 Java
LeetCode第28题找出字符串中第一个匹配项的下标
这篇文章介绍了LeetCode第28题"找出字符串中第一个匹配项的下标"的两种解法:暴力解法和KMP算法,并解释了KMP算法通过构建前缀表来提高字符串搜索的效率。
LeetCode第28题找出字符串中第一个匹配项的下标
|
3月前
|
算法
LeetCode第8题字符串转换整数 (atoi)
该文章介绍了 LeetCode 第 8 题字符串转换整数 (atoi)的解法,需要对字符串进行格式解析与校验,去除前导空格和处理正负号,通过从高位到低位的计算方式将字符串转换为整数,并处理越界情况。同时总结了这几道题都需要对数字的表示有理解。
LeetCode第8题字符串转换整数 (atoi)