字符串解码
题目要求
给定一个字符串，这个字符串包含一些特定的编码规则。这些规则定义了如何重复字符串中的某些部分。具体来说，编码规则遵循这样的格式：k[encoded_string]，这里的 k 是一个正整数，encoded_string 是需要被重复的字符串。当解码时，我们需要将 encoded_string 重复 k 次。
例如，字符串 "3[a]2[bc]" 解码后应该变成 "aaabcbc"。
解码的过程需要遵循以下几个原则：
- 输入的字符串总是有效的，不包含任何额外的空格。
- 方括号总是成对出现，并且格式正确。
- 原始数据（即不在方括号内的数据）不包含数字，数字总是表示重复次数。
- 输入的字符串可能包含嵌套的编码规则，例如 "2[3[a]b]"，解码后应该变成 "aaabaaab"。
解题思路
要解决这个问题，我们可以采用栈（Stack）的数据结构来处理。栈是一种后进先出（LIFO）的数据结构，它可以帮助我们在遇到嵌套结构时保持跟踪状态。
- 初始化两个栈：一个用于保存数字（即重复次数），另一个用于保存当前处理的字符串。
- 遍历输入字符串：对于每个字符，我们需要根据其类型执行不同的操作：
- 如果是数字，我们需要计算出完整的数字（因为数字可能有多位），然后将其压入数字栈。
- 如果是字母，我们将其添加到当前处理的字符串中。
- 如果遇到左方括号 '['，说明我们遇到了一个新的 encoded_string 的开始，我们需要将当前的字符串压入栈中，并且重置当前字符串，以便于收集新的 encoded_string。
- 如果遇到右方括号 ']'，说明一个 encoded_string 结束了，我们需要进行解码操作。这时，我们将数字栈的栈顶元素弹出，这个数字表示重复次数。然后我们将字符串栈的栈顶元素弹出，这是之前累积的字符串。我们将当前处理的字符串重复弹出的数字次数，然后将其与弹出的字符串拼接，作为新的当前处理的字符串。
- 重复步骤 2，直到遍历完整个输入字符串。
- 返回结果：遍历结束后，当前处理的字符串即为解码后的字符串。
通过这种方式，我们可以逐步构建出最终的解码字符串，即使在存在嵌套的情况下也能正确处理。
Golang 版本
package main
import (
"strconv"
"strings"
"unicode"
)
func decodeString(s string) string {
var numStack []int
var strStack []string
var currentNum int
var currentStr string
for _, char := range s {
if unicode.IsDigit(char) {
// Parse the number and update currentNum
num, _ := strconv.Atoi(string(char))
currentNum = currentNum*10 + num
} else if char == '[' {
// Push the currentNum and currentStr to their respective stacks
numStack = append(numStack, currentNum)
strStack = append(strStack, currentStr)
// Reset currentNum and currentStr
currentNum = 0
currentStr = ""
} else if char == ']' {
// Pop the number from numStack to get the repeat times
repeatTimes := numStack[len(numStack)-1]
numStack = numStack[:len(numStack)-1]
// Pop the string from strStack and append the currentStr repeated repeatTimes
prevStr := strStack[len(strStack)-1]
strStack = strStack[:len(strStack)-1]
currentStr = prevStr + strings.Repeat(currentStr, repeatTimes)
} else {
// Append the current character to currentStr
currentStr += string(char)
}
}
return currentStr
}
func main() {
// Example usage:
encodedString := "3[a]2[bc]"
decodedString := decodeString(encodedString)
println(decodedString) // Output: aaabcbc
}
这段代码定义了一个decodeString函数，它接受一个编码的字符串并返回解码后的字符串。在main函数中，我们提供了一个示例用法，调用decodeString函数并打印结果。
C++版本
#include <iostream>
#include <stack>
#include <string>
std::string decodeString(const std::string& s) {
std::stack<int> counts;
std::stack<std::string> result;
std::string currentStr;
int k = 0;
for (char ch : s) {
if (isdigit(ch)) {
k = k * 10 + (ch - '0');
} else if (ch == '[') {
counts.push(k);
result.push(currentStr);
currentStr = "";
k = 0;
} else if (ch == ']') {
std::string temp = result.top();
result.pop();
for (int i = counts.top(); i > 0; --i) {
temp += currentStr;
}
counts.pop();
currentStr = temp;
} else {
currentStr += ch;
}
}
return currentStr;
}
int main() {
std::string encodedString = "3[a]2[bc]";
std::string decodedString = decodeString(encodedString);
std::cout << decodedString << std::endl; // Output: aaabcbc
return 0;
}
这段 C++代码实现了一个decodeString函数，它接收一个编码的字符串并返回解码后的字符串。在main函数中，我们提供了一个示例用法，调用decodeString函数并打印结果。
Python 版本
def decodeString(s):
stack = []
current_num = 0
current_string = ''
for char in s:
if char.isdigit():
current_num = current_num * 10 + int(char)
elif char == '[':
stack.append((current_string, current_num))
current_string = ''
current_num = 0
elif char == ']':
last_string, num = stack.pop()
current_string = last_string + num * current_string
else:
current_string += char
return current_string
# Example usage:
encoded_string = "3[a]2[bc]"
decoded_string = decodeString(encoded_string)
print(decoded_string) # Output: aaabcbc
这段 Python 代码定义了一个decodeString函数，它接受一个编码的字符串并返回解码后的字符串。在示例用法中，我们调用decodeString函数并打印结果。
Java 版本
import java.util.Stack;
public class Solution {
public String decodeString(String s) {
Stack<Integer> countStack = new Stack<>();
Stack<StringBuilder> stringStack = new Stack<>();
StringBuilder currentString = new StringBuilder();
int k = 0;
for (char ch : s.toCharArray()) {
if (Character.isDigit(ch)) {
k = k * 10 + (ch - '0');
} else if (ch == '[') {
countStack.push(k);
stringStack.push(currentString);
currentString = new StringBuilder();
k = 0;
} else if (ch == ']') {
StringBuilder decodedString = stringStack.pop();
for (int currentK = countStack.pop(); currentK > 0; currentK--) {
decodedString.append(currentString);
}
currentString = decodedString;
} else {
currentString.append(ch);
}
}
return currentString.toString();
}
public static void main(String[] args) {
Solution solution = new Solution();
String encodedString = "3[a]2[bc]";
String decodedString = solution.decodeString(encodedString);
System.out.println(decodedString); // Output: aaabcbc
}
}
这段 Java 代码定义了一个Solution类，其中包含一个decodeString方法，用于解码给定的字符串。在main方法中，我们创建了Solution类的实例，并调用decodeString方法，然后打印出解码后的字符串。
Rust 版本
use std::str::Chars; use std::iter::Peekable; fn decode_string(s: &str) -> String { let mut chars_iter = s.chars().peekable(); decode(&mut chars_iter) } fn decode(chars_iter: &mut Peekable<Chars>) -> String { let mut result = String::new(); let mut num = 0; while let Some(&ch) = chars_iter.peek() { match ch { '0'..='9' => { num = num * 10 + ch.to_digit(10).unwrap(); chars_iter.next(); } '[' => { chars_iter.next(); // skip '[' let part = decode(chars_iter); for _ in 0..num { result.push_str(&part); } num = 0; } ']' => { chars_iter.next(); // skip ']' break; } _ => { result.push(ch); chars_iter.next(); } } } result } fn main() { let encoded_string = "3[a]2[bc]"; let decoded_string = decode_string(encoded_string); println!("{}", decoded_string); // Output: aaabcbc }
这段 Rust 代码定义了一个decode_string函数，它接受一个编码的字符串并返回解码后的字符串。decode函数是一个辅助函数，它使用递归来处理嵌套的编码字符串。在main函数中，我们调用decode_string函数并打印结果。
总结
上述解法遵循了一个通用的算法框架，适用于多种编程语言。核心思想是使用两个栈：一个用于保存数字（即重复次数），另一个用于保存当前构建的字符串。算法的步骤如下：
- 遍历输入字符串中的每个字符。
- 当遇到数字时，计算出完整的数字（可能有多位），并将其保存在数字栈中。
- 遇到左括号 '[' 时，将当前的数字（重复次数）和当前构建的字符串分别压入各自的栈中，然后重置这两个变量，准备解析新的字符串片段。
- 遇到右括号 ']' 时，从数字栈中弹出一个数字，表示重复次数；从字符串栈中弹出一个字符串，表示之前累积的字符串。将当前构建的字符串重复相应的次数，并拼接到弹出的字符串后面，更新当前字符串。
- 遇到字母时，将其追加到当前构建的字符串中。
- 继续遍历，直到处理完所有字符。
- 最终，当前构建的字符串即为解码后的字符串。
这个算法在不同的编程语言中实现时，主要的区别在于语法和数据结构的使用。例如，在 Python 中使用列表来模拟栈的操作，在 C++中使用std::stack，在 Java 中使用Stack类，在 Rust 中使用Vec作为栈，并利用迭代器和模式匹配来简化代码。尽管实现细节不同，但所有版本的核心算法逻辑是一致的。