Leetcode 字符串解码

该代码的算法思想可以分为以下几个步骤：

1. 使用栈来处理嵌套结构：

• 我们需要处理像 k[encoded_string] 这种格式，其中的 encoded_string 可能是嵌套的，即像 3[a2[c]] 这样的输入。因此，我们可以借助 栈（Stack）来记录每一层的状态，处理嵌套的情况。

2. 两个栈来分别保存重复次数和当前字符串：

• countStack: 用来保存当前需要重复的次数 k。每遇到一个 [，就表示有一个新的重复次数需要记录下来。
• resultStack: 用来保存每次遇到 [ 之前生成的字符串（即之前的部分字符串），以便遇到 ] 时能把当前处理的部分和之前的部分结合起来。

3. 遍历字符串并根据字符类型进行处理：

• 数字：当遇到数字时，可能会有多位数字组合在一起（例如 “10” 或 “100”），因此需要将完整的数字解析出来，并将它压入 countStack。
• 左括号 [：当遇到 [ 时，表示进入一个新的子问题，将当前已生成的字符串 result 存入 resultStack，并将 result 重置为空字符串，准备处理括号内的部分。
• 右括号 ]：当遇到 ] 时，说明当前括号内的子字符串已经生成完毕，应该将其重复相应的次数（根据 countStack 中的值），然后将重复后的结果与之前保存的部分字符串拼接起来。
• 字母：如果当前字符是字母（既不是数字，也不是括号），则直接将其附加到当前的 result 中。

4. 算法流程：

• 代码从头到尾遍历字符串：
  • 遇到数字时解析出完整的数字，并压入 countStack。
  • 遇到 [ 时，将当前字符串保存到 resultStack 并清空 result。
  • 遇到 ] 时，弹出 countStack 和 resultStack 的内容，生成重复的字符串并拼接起来。
  • 遇到普通字符时，将其附加到当前的 result 中。

5. 最终结果：

• 遍历完所有字符后，result 中存储的就是最终解码后的字符串。

例子分析：

以输入 s = "3[a2[c]]" 为例：

• 首先解析出数字 3，然后遇到 [，将当前的 result（空字符串）压入 resultStack。
• 继续遇到 a，将其加到 result 中。
• 然后遇到 2，解析出数字 2，遇到 [，将当前的 result (a) 压入 resultStack。
• 遇到 c，将其加到 result 中，接着遇到 ]，从 countStack 中弹出 2，将 c 重复两次并与 resultStack 中的 a 拼接，得到 acc。
• 最后遇到 ]，将 acc 重复三次，得到最终结果 accaccacc。

复杂度分析：

• 时间复杂度: 每个字符都被处理一次，因此时间复杂度为 O(n)，其中 n 是输入字符串的长度。
• 空间复杂度: 由于使用了栈来存储中间结果，最坏情况下栈的深度为嵌套层数，因此空间复杂度也是 O(n)。

这样设计的算法能高效处理带有多层嵌套和重复的字符串解码问题。

class Solution {
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<String> resultStack = new Stack<>();
        int index = 0;
        String result = "";
        while(index < s.length()) {
            if(Character.isDigit(s.charAt(index))) {
                int count = 0;
                while(Character.isDigit(s.charAt(index))) {
                    count = count * 10 + (s.charAt(index) - '0'); //将连续数字字符转换为int数值
                    index++; //注意,index的位置是在while循环内部更新，而不是while循环外部
                }
                countStack.push(count);
            }else if(s.charAt(index) == '[') {
                resultStack.push(result);
                result = "";
                index++;
            }else if(s.charAt(index) == ']') {
                StringBuilder temp = new StringBuilder(resultStack.pop());
                int repeatTimes = countStack.pop();
                for(int i = 0; i < repeatTimes; ++i) {
                    temp.append(result); //temp一直在append并没有被清空过
                }
                //result 是增量式变化
                result = temp.toString();
                index++;
            }else {
                result = result + s.charAt(index);
                index++;
            }
        }
        return result;
    }
}

为什么在遇到[时，将当前字符串保存到 resultStack 并清空 result，这是因为第一次遇到[时，当前字符串是空串""，除了第一次，之后每次遇到[时，当前字符串都是上一个[]中的完整字符串，所以需要将当前字符串保存到 resultStack 并清空 result

你理解得非常正确！在遇到 [ 时，将当前字符串保存到 resultStack 并清空 result 是算法中的一个关键步骤，原因可以从以下几个方面解释：

1. 处理嵌套结构：

每次遇到 [ 时，说明即将开始处理一个新的子字符串，而当前的 result 中已经存储了上一个部分（或者是空串，如果是第一次遇到 [）。为了确保可以正确地将嵌套结构解析并组合在一起，需要先将当前的 result 暂时保存起来，等待后续处理完括号内的子字符串后再恢复。

2. 保存当前结果用于拼接：

• 第一次遇到 [ 时，当前的 result 可能是空串 ""，因为还没有处理到任何有效的字符。将空串压入 resultStack 只是为了保持结构一致。
• 之后每次遇到 [ 时，当前的 result 已经包含了在之前解析的字符串。例如，对于输入 "2[abc]3[cd]ef"，当处理到 3[ 时，result 可能是 "abcabc"，这时需要将它保存到 resultStack，以便之后拼接 cd 重复的部分。

3. 清空 result 以处理括号内的新内容：

每次遇到 [ 后，新的字符串解析会从括号内部的内容开始，因此必须将 result 清空，确保解析的新字符串（括号内的部分）不会与之前的内容混在一起。这样做的目的是为每一对 [] 保持独立的处理状态。

例子解释：

假设我们处理字符串 s = "2[abc]3[cd]ef"：

1. 遇到 2，我们解析出 count = 2。
2. 遇到 [，我们把当前的 result（空串）压入 resultStack，然后清空 result，为接下来解析 abc 做准备。
3. 解析到 abc，此时 result = "abc"。
4. 遇到 ]，我们从 resultStack 中弹出空串，重复 abc 两次，得到 "abcabc"，并将其保存到 result。
5. 继续处理 3[cd] 时，result = "abcabc"，我们需要保存它，因此再次遇到 [ 时，将 "abcabc" 压入 resultStack，清空 result 以解析 cd。
6. 解析 cd 完成后，我们将 result = "cdcdcd" 与之前的 "abcabc" 拼接，得到 "abcabccdcdcd"。
7. 最后，添加 ef，得到最终结果 "abcabccdcdcdef"。

总结：

每次遇到 [ 时，将当前的 result 保存到 resultStack，并清空 result 是为了：

• 确保每个括号对内的字符串能够独立解析。
• 保证括号内的字符串能够正确重复并与之前的部分拼接。

这一步处理使得代码可以正确解析嵌套和连续的编码字符串。

之所以使用StringBuilder temp, 是因为temp一直在append并且temp不会被清空，所以result = temp.toString();是增量式变化的

是的，完全正确！你对 StringBuilder temp 的使用理解非常到位。

使用 StringBuilder 和 temp.append(result) 是为了增量式地构建字符串，并且 temp 不会在每次循环中被清空，它会逐步构建最终的解码结果。具体原因如下：

1. StringBuilder 提供高效的字符串拼接操作：

• StringBuilder 是 Java 中用于高效处理字符串拼接的类，因为它不像 String 那样每次拼接都会创建一个新的字符串对象。使用 StringBuilder 可以避免频繁创建新对象，提升性能，特别是在循环中拼接大量字符串的情况下。

2. temp 用于存储多次拼接后的结果：

• 在 while 循环中，当遇到 ] 时，会把 resultStack 中保存的上一级的字符串取出，并将当前解析的 result 重复多次后，拼接回到 temp 中。
• 每次进入这个步骤时，temp 会不断通过 temp.append(result) 增量式地拼接新的部分，而不会被清空。
• 注意：result 只存储当前括号内的部分，而 temp 逐渐积累最终结果。

3. 增量式的变化：

• 每次遇到 ] 时，temp.append(result) 的结果会不断累积。然后使用 result = temp.toString(); 将 temp 中的累积结果转换回 String 类型并赋给 result，继续后续的处理。
• temp 不会在循环中被清空，因此它能够保存之前的拼接结果，从而实现增量式的构建。

例子分析：

假设输入是 s = "3[a2[c]]"，解析过程如下：

1. 解析到 3[，开始处理 a2[c]，此时 result = ""。
2. 解析到 a，result = "a"。
3. 解析到 2[c]，进入内层括号，先把 result = "a" 压入 resultStack，然后清空 result 准备处理 c。
4. 解析到 c，result = "c"，之后遇到 ]，弹出 2，将 c 重复两次，得到 cc，将其与 resultStack 中的 "a" 拼接，生成 temp = "acc"。
5. 最后，处理 3[] 的外层，弹出 3，将 "acc" 重复三次，通过 temp.append(result) 得到 accaccacc，最终将其赋值给 result。

因此，temp 是不断积累的，而 result 在不同层次的括号内会被清空并重新构建，这样的设计确保了各层括号中的字符串能够正确拼接到一起。

总结：

• StringBuilder temp 用来增量式地拼接字符串，每次重复操作后都把结果追加到 temp，这样可以避免频繁创建新对象，并且不会在循环中被清空。
• result = temp.toString(); 只是把 StringBuilder 中的累积结果转换成字符串后继续后续的处理。
• 这种设计确保每层括号解析完后，拼接结果能够累积并正确组合，最终得到完整的解码字符串。

原文地址：https://blog.csdn.net/coldasice342/article/details/143063076

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！