394 字符串编码

  1. 394. 字符串解码
  2. 给定一个经过编码的字符串，返回它解码后的字符串。
  4. 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
  6. 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
  8. 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
  12. 示例 1：
  14. 输入：s = "3[a]2[bc]"
  15. 输出："aaabcbc"
  16. 示例 2：
  18. 输入：s = "3[a2[c]]"
  19. 输出："accaccacc"
  20. 示例 3：
  22. 输入：s = "2[abc]3[cd]ef"
  23. 输出："abcabccdcdcdef"
  24. 示例 4：
  26. 输入：s = "abc3[cd]xyz"
  27. 输出："abccdcdcdxyz"
  • js 解法
  1. /**
  2.  * @param {string} s
  3.  * @return {string}
  4.  */
  5. var decodeString = function (s) {
  6.     let numStack = [];
  7.     let strStack = [];
  8.     let num = 0;
  9.     let result = "";
  10.     for (let char of s) {
  11.         if (!isNaN(char)) {
  12.             num = num * 10 + Number(char);
  13.         } else if (char === "[") {
  14.             numStack.push(num);
  15.             num = 0;
  16.             strStack.push(result);
  17.             result = "";
  18.         }else if(char ==="]"){
  19.             let repeatNum = numStack.pop();
  20.             result = strStack.pop() + result.repeat(repeatNum);
  21.         }else{
  22.             result += char;
  23.         }
  24.     }
  25.     return result;
  26. };
  • 时间复杂度：O(N)
  • 空间复杂度：O(N)
  • js递归解法暂无
  • java 解法
  1. class Solution {
  2.     public String decodeString(String s) {
  3.         StringBuilder res = new StringBuilder();
  4.         int multi = 0;
  5.         LinkedList<Integer> stack_multi = new LinkedList<>();
  6.         LinkedList<String> stack_res = new LinkedList<>();
  7.         for(Character c : s.toCharArray()) {
  8.             if(c == '[') {
  9.                 stack_multi.addLast(multi);
  10.                 stack_res.addLast(res.toString());
  11.                 multi = 0;
  12.                 res = new StringBuilder();
  13.             }
  14.             else if(c == ']') {
  15.                 StringBuilder tmp = new StringBuilder();
  16.                 int cur_multi = stack_multi.removeLast();
  17.                 for(int i = 0; i < cur_multi; i++) tmp.append(res);
  18.                 res = new StringBuilder(stack_res.removeLast() + tmp);
  19.             }
  20.             else if(c >= '0' && c <= '9') multi = multi * 10 + Integer.parseInt(c + "");
  21.             else res.append(c);
  22.         }
  23.         return res.toString();
  24.     }
  25. }