网络异常,图片无法展示
|
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: 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-字符串解码
如有任何问题或建议,欢迎留言讨论!