当前位置：首页 > article >正文

一起学习LeetCode热题100道（71/100）

article 2024/9/20 15:02:19

71.字符串解码(学习)

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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”

提示：
1 <= s.length <= 30
s 由小写英文字母、数字和方括号 ‘[]’ 组成
s 保证是一个有效的输入。
s 中所有整数的取值范围为 [1, 300]

解析：
一、初始化
1.stack：一个空数组，用于存储临时对象，每个对象包含两个属性：str（当前括号块之前的字符串）和times（该字符串应该被重复的次数）。
2.currentString：一个空字符串，用于构建当前正在处理的字符串片段。
3.multiplier：一个整数，初始化为0，用于累积当前遇到的数字，表示重复次数。

二、遍历输入字符串
对于字符串s中的每个字符，执行以下操作：
1.数字处理：
1.1.如果当前字符是数字（!isNaN(char)），则将其转换为整数并累加到multiplier上。注意，这里使用了parseInt(char, 10)来确保即使char是字符串形式的数字也能正确转换。但在实际代码中，由于我们已经通过!isNaN(char)确保了char是数字，所以直接使用parseInt(char)或简单地multiplier = multiplier * 10 + parseInt(char.charCodeAt(0) - ‘0’.charCodeAt(0))（利用字符编码差计算）也是可以的。
2.左括号[处理：
2.1.当遇到左括号[时，表示一个新的编码块开始。此时，我们需要将当前已经构建的字符串currentString和当前的重复次数multiplier作为一个对象压入stack中，以便后续处理。然后，重置currentString为空字符串，以便开始构建新的字符串片段，同时重置multiplier为0，以准备计算下一个重复次数。
3.右括号]处理：
3.1.当遇到右括号]时，表示一个编码块的结束。此时，我们从stack中弹出一个对象，该对象包含了该编码块之前的字符串str和该字符串应该被重复的次数times。然后，我们将currentString（即当前编码块内的字符串）重复times次，并将结果附加到str的末尾（注意，由于我们是从内向外解析的，所以需要将currentString附加到str的前面，但因为我们是在构建currentString，所以实际上是将其加到str重复后的字符串之后）。最后，更新currentString为这个新构建的字符串，以便后续可能的处理。
4.其他字符处理：
4.1.如果当前字符既不是数字也不是括号，那么它就是编码字符串的一部分。我们简单地将它附加到currentString的末尾。

三、返回结果
1.遍历完成后，currentString将包含解码后的完整字符串。我们返回这个字符串作为函数的结果。

var decodeString = function (s) {
    let stack = [], // 用于存储结果字符串  
        currentString = '', // 当前正在构建的字符串  
        multiplier = 0; // 当前重复次数  

    for (let i = 0; i < s.length; i++) {
        const char = s[i];

        if (!isNaN(char)) { // 如果是数字，则构建重复次数  
            multiplier = multiplier * 10 + parseInt(char, 10);
        } else if (char === '[') { // 遇到 '['，将当前字符串和重复次数入栈  
            stack.push({ str: currentString, times: multiplier });
            currentString = ''; // 重置当前字符串  
            multiplier = 0; // 重置重复次数  
        } else if (char === ']') { // 遇到 ']'，根据栈顶元素重复字符串  
            const { str, times } = stack.pop();
            currentString = str + currentString.repeat(times); // 注意这里要将当前字符串加到前面  
        } else { // 其他字符，直接加到当前字符串  
            currentString += char;
        }
    }

    return currentString; // 返回最终构建的字符串  
};