网络异常，图片无法展示
|
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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" 复制代码
递归解题
解题思路
- 首先特判，如果输入字符串中没有中括号，则当前字符不需要解码，直接返回（即递归的终止条件）。
- 初始化
num记录k值，stack记录左括号下标，res记录结果字符串。 - 遍历输入字符串，如果当前字符为左括号，将其下标入栈。
- 如果栈为空，当前字符为数字，组装
num,当前字符为非数字，将字符拼接到结果字符串后。 - 如果当前字符为右括号，则将栈顶元素弹出。如果弹栈后栈为空，则说明找到了一组最外层括号，截取中间部分字符，并重复对应
num次，利用decodeString函数递归处理，并将处理后的结果拼接到结果字符串后。 - 如此遍历完输入字符串，
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; }; 复制代码
迭代解题
解题思路
- 初始化栈为空。
- 遍历输入字符串，如果当前字符为数字，获取对应数字并入栈。
- 如果当前字符为右括号，将栈顶字符弹出，组成字符串，直到遇到与之对应的左括号。此时，字符串中保存的就是括号中间部分，再将栈顶元素弹出，此时栈顶元素就是该部分编码字符对应的
k值，将字符串重复k次，并将结果再次入栈。 - 其他字符直接入栈。
- 最后将栈中的字符串拼接为一个字符串，就是解码后的字符串。
动画演示
网络异常，图片无法展示
|
代码实现
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-字符串解码
如有任何问题或建议，欢迎留言讨论！
