跳到主要内容

编码解码题库

一、字符串编码​

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

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

1.1 通过栈​

思路: 本题难点在于括号内嵌套括号，需要从内向外生成与拼接字符串，这与栈的先入后出特性对应。

  • 构建辅助栈 stack， 遍历字符串 s 中每个字符 c；
  • 当 c 为数字时，将数字字符转化为数字 multi，用于后续倍数计算；
  • 当 c 为字母时，在 res 尾部添加 c；
  • 当 c 为 [ 时，将当前 multi 和 res 入栈，并分别置空置 00：
    • 记录此 [ 前的临时结果 res 至栈，用于发现对应 ] 后的拼接操作；
    • 记录此 [ 前的倍数 multi 至栈，用于发现对应 ] 后，获取 multi × [...] 字符串。
    • 进入到新 [ 后，res 和 multi 重新记录。
  • 当 c 为 ] 时，stack 出栈，拼接字符串 res = last_res + cur_multi * res，其中:
    • last_res是上个 [ 到当前 [ 的字符串，例如 "3[a2[c]]" 中的 a；
    • cur_multi是当前 [ 到 ] 内字符串的重复倍数，例如 "3[a2[c]]" 中的 2。
  • 返回字符串 res。

重复如上操作，最终将栈中的元素按照从栈底到栈顶的顺序拼接起来，就得到了答案

:::details 点击查看代码

function decodeString(s) {
    let res=[];
    let multi=0;
    let stack_multi=[];
    let stack_res=[];
    for(let i=0;i<s.length;i++){
        if(s[i]=='['){
            stack_multi.push(multi);
            stack_res.push(res.join(''));
            multi=0;
            res=[];
        }else if(s[i]==']'){
            let temp=[];
            let current_multi=stack_multi.pop();
            for(let i=0;i<current_multi;i++){
                temp.push(res.join(''));
            }
            res=[stack_res.pop()+temp.join('')];
        }else if(s[i]>='0'&&s[i]<='9'){
            multi=multi*10+Number(s[i])
        }else{
            res.push(s[i]);
        }
    }
    return res.join('');
};

:::

性能分析:

  • 时间复杂度 O(N)，一次遍历 s；
  • 空间复杂度 O(N)，辅助栈在极端情况下需要线性空间，例如 2[2[2[a]]]。

1.2 递归法​

思路: 总体思路与辅助栈法一致，不同点在于将 [ 和 ] 分别作为递归的开启与终止条件：

  • 当 s[i] == ']' 时，返回当前括号内记录的 res 字符串与 ] 的索引 i （更新上层递归指针位置）；
  • 当 s[i] == '[' 时，开启新一层递归，记录此 [...] 内字符串 tmp 和递归后的最新索引 i，并执行 res + multi * tmp 拼接字符串。
  • 遍历完毕后返回 res。

:::details 点击查看代码

function decodeString(s) {
    const dfs=(s,i)=>{
    let result=[];
    let multi=0;
    while(i<s.length){
        if(s[i]>=0&&s[i]<=9){
            multi=multi*10+Number(s[i]);
        }else if(s[i]=='['){
            let temp=dfs(s,i+1);
            i=temp[0];
            while(multi>0){
                result.push(temp[1]);
                multi--;
            }
        }else if(s[i]==']'){
            return [i,result.join('')];
        }else{
            result.push(s[i]);
        }
        i++;
    }
    return [result.join('')]
    }
    return dfs(s,0)[0];
};

:::

性能分析:

  • 时间复杂度 O(N)，递归会更新索引，因此实际上还是一次遍历 s；
  • 空间复杂度 O(N)，极端情况下递归深度将会达到线性级别。

二、解码方法​

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> 1
'B' -> 2
...
'Z' -> 26

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

"AAJF" ，将消息分组为 (1 1 10 6) "KJF" ，将消息分组为 (11 10 6) 注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例1:

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例2:

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例3:

输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。

示例4:

输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。

2.1 动态规划​

思路: 总的来说, 这个解法通过判断每个位置上的单个字符和相邻两个字符是否能构成有效的编码, 从而利用之前计算的状态来更新当前状态, 实现了线性时间复杂度和常数空间的解法。

一、初始化:

  • 变量 a 代表 dp[i-2]（上上一个状态），初始为 0。

  • 变量 b 代表 dp[i-1]（上一个状态），初始为 1。这里设为 1 是为了方便在没有字符（空字符串）时认为有一种解码方式。

  • 变量 c 用来存储当前状态 dp[i] 的值。我们用 dp[i] 表示前 i 个字符能解码成多少种不同的方式。最终的目标是求 dp[n]，其中 n 是字符串的长度。

二、遍历字符串: 从 i = 1 开始遍历到 n（注意字符串索引从 0 开始，所以实际处理的字符是 str[i-1]）。每次循环时, 先将 c 重置为 0, 表示当前的解码方式数还未计算。

  • 单个字符的情况: 如果 str[i-1] 不等于 0（因为 0 不能单独解码），那么当前字符可以独立解码, 这时累加 b（即上一个状态 dp[i-1]）到 c 上。这相当于：如果当前字符可以单独构成一个字母, 那么所有以 i-1 个字符的解码方式都可以在后面加上这个字母。

  • 两个字符的情况: 当 i > 1 时，判断前一个字符 str[i-2] 是否不为 0（如果为 0，则无法和后面的数字组合）以及两个字符组成的数字是否小于等于 26（满足编码规则）。如果满足条件, 那么累加 a（即 dp[i-2]）到 c 上。这相当于: 如果前后两个字符可以组成一个有效的字母（例如 12 对应字母 L），那么所有以 i-2 个字符的解码方式都可以在后面加上这两个字符组合成的字母。

三、状态更新: 将 a 更新为原来的 b，将 b 更新为当前的 c。这样就将状态往前推进一步，准备计算下一个字符位置的状态。

四、返回结果: 循环结束后, 变量 c 中存放的就是 dp[n], 即整个字符串的解码方式数, 返回这个值即可。

function numDecodings(str) {
  let a = 0;
  let b = 1;
  let c = 0;

  for (let i = 0; i <= str.length; i++) {
    c = 0;

    if (str[i - 1] != 0) {
      c += b;
    }

    if (
      i > 1 &&
      str[i - 2] != 0 &&
      Number(str[i - 2]) * 10 + Number(str[i - 1]) <= 26
    ) {
      c += a;
    }

    a = b;
    b = c;
  }

  return c;
}