编码解码题库

字符串编码

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

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

方案A 通过栈

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

构建辅助栈 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]]]。

方案B 递归法

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

当 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" 在映射中并不等价）。

方案动态规划

思路:对于给定的字符串 s，设它的长度为 n，其中的字符从左到右依次为 s[n]s[1],s[2],⋯,s[n]。我们可以使用动态规划的方法计算出字符串 s 的解码方法数。

状态定义: 设 dp[i] 表示字符串 s 的前 i 个字符 s[1..i] 的解码方法数
状态转移方程: 在进行状态转移时，我们可以考虑最后一次解码使用了 s 中的哪些字符，那么会有下面的两种情况:
- 第一种情况是我们使用了一个字符，即 s[i] 进行解码，那么只要 s[i]!=0，它就可以被解码成 A∼I 中的某个字母。由于剩余的前 i-1 个字符的解码方法数为 i−1，因此我们可以写出状态转移方程：dp[i]=dp[i-1](s[i]!=0)
- 第二种情况是我们使用了两个字符，即 s[i-1] 和 s[i] 进行编码。与第一种情况类似，s[i−1] 不能等于 0，并且 s[i-1] 和 s[i] 组成的整数必须小于等于 26，这样它们就可以被解码成 J∼Z 中的某个字母。由于剩余的前 i-2 个字符的解码方法数为 i−2，因此我们可以写出状态转移方程：dp[i]=dp[i-2](s[i]!=0&&10⋅s[i−1]+s[i]≤26)
状态初始化: dp 元素默认为 0 ，dp[0]=1 即空字符串可以有 1 种解码方法，解码出一个空字符串。

:::details 优化空间前

function numDecodings(s) {
    let dp=new Array(s.length+1).fill(0);
    dp[0]=1;
    for(let i=1;i<=s.length;i++){
        if(s[i-1]!=='0'){
            dp[i]+=dp[i-1];
        }
        if(i>1&&s[i-2]!=='0'&&((s[i-2]-'0')*10)+(s[i-1]-'0')<=26){
            dp[i]+=dp[i-2];
        }
    }
    return dp[s.length];
};

:::

注意到在状态转移方程中，dp[i] 的值仅与 dp[i-1] 和 dp[i-2] 有关，因此我们可以使用三个变量进行状态转移，省去数组的空间。

:::details 优化空间后

function numDecodings(s) {
    let dp1=1;
    let dp2=0;
    let result=0;
    for(let i=1;i<=s.length;i++){
        result=0;
        if(s[i-1]!=='0'){
            result+=dp1;
        }
        if(i>1&&s[i-2]!=='0'&&((s[i-2]-'0')*10)+(s[i-1]-'0')<=26){
            result+=dp2;
        }
        dp2=dp1;
        dp1=result;
    }
    return result;
};

:::

性能分析:

时间复杂度：O(n)，其中 n 是字符串 s 的长度。
空间复杂度：O(n) 或 O(1)。如果使用数组进行状态转移，空间复杂度为 O(n)；如果仅使用三个变量，空间复杂度为 O(1)。

字符串编码​

方案A 通过栈​

方案B 递归法​

解码方法​

方案 动态规划​

字符串编码

方案A 通过栈

方案B 递归法

解码方法

方案动态规划