394. 字符串解碼

給定一個經過編碼的字符串，返回它解碼后的字符串。

示例 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”

這道題目感覺很不好做，我自己的解法很復雜，而且過不去一個測試點：

class Solution {
public:string decodeString(string s) {stack<string> st;int k = 0;string mode = "";string currentStr = "";for (char c : s) {if (isdigit(c)) {if (mode != "") {st.push(mode);mode = "";}k = k * 10 + c - '0';} else if (isalpha(c)) {if (k != 0) {st.push(to_string(k));k = 0;}mode += c;} else if (c == ']') { // 退棧、合并if (stringIsNum(st.top())) {// 如果棧頂是數字int num = stoi(st.top());st.pop();currentStr = mode;for (int i = 0; i < num - 1; i++) {currentStr += mode;}st.push(currentStr);currentStr = "";mode = "";} else { // 否則合并currentStr = st.top();st.pop();currentStr += mode;st.push(currentStr);currentStr = "";mode = "";}} else if (c == '[') {if (k != 0) {st.push(to_string(k));k = 0;}}}if (mode != "")st.push(mode);// 最后的處理currentStr = "";while (!st.empty()) {string topStr = st.top();st.pop();if (st.empty())return topStr;if (stringIsNum(st.top())) {currentStr = topStr;int num = stoi(st.top());st.pop();for (int i = 0; i < num - 1; i++) {currentStr += topStr;}st.push(currentStr);currentStr = "";} else {currentStr = topStr;topStr = st.top();currentStr = topStr + currentStr;st.pop();st.push(currentStr);}}return "";}private:bool stringIsNum(string& str) {try {int num = std::stoi(str);return true;} catch (const std::invalid_argument& e) {return false;}}
};

后面我想到了用兩個棧來解決這個問題，其中一個棧用來存儲字符串段，另一個棧用來存儲字符串段重復的次數。接下來的重點就是處理'['、']'符號。

示例1：

對于s = "3[a]2[bc]"：遇到'['的時候，入棧數字以及當前currentStr，并且置空；遇到']'的時候，取字符串段的 top 元素、重復次數棧的 top 元素，然后進行拼接。重復這個過程，currentStr 就是答案。

示例2：

對于s = "3[a2[c]]"：也是同樣的操作。

class Solution {
public:string decodeString(string s) {stack<int> counts;     // 用于存儲重復次數stack<string> strings; // 用于存儲字符串段int k = 0;string currentStr = "";for (char c : s) {if (isdigit(c)) {k = k * 10 + (c - '0');} else if (isalpha(c)) {currentStr += c;} else if (c == '[') {// 遇到 '[' 時，將之前的數字和字符串推入棧中counts.push(k);strings.push(currentStr);k = 0;currentStr = "";} else if (c == ']') {// 遇到 ']' 時，開始構建字符串string temp = currentStr;currentStr = strings.top(); // 取出之前的字符串strings.pop();int count = counts.top(); // 取出重復次數counts.pop();for (int i = 0; i < count; i++) {currentStr += temp;}}}return currentStr; // 返回最終構建的字符串}
};

不禁要問，為什么可以這樣？這里不禁讓我想起了離散數學中的群論中的知識點，下面詳細分析下。

• 操作數：我們首先定義操作數，很明顯這里的操作數為 string 以及 int。
• 操作：這里并沒有明確表明操作符號是什么，但是可以推斷隱含的操作符。當 int[string] 時，表明要將 string 重復 int 次；當 stringstring 的時候，表明它們需要拼接；至于string int這種運算不存在，因為 int 必須后面跟 string。

因此，遇到'['的時候，這意味著將要計算int[string]，將數字入棧，而且在數字入棧意味著數字前面還有一個 string ，不管這個 string 是否為空，無所謂。當遇到']'的時候，意味著int[string]要進行拼接了。

可以看到，這個道題目無非就是計算int[string]以及stringstring，因此這道題目和+、*混合運算同構。

對于s = "3[a]2[bc]"：可以同構為：s = 3*(a)+2*(bc)；對于s = "3[a2[c]]"，則可以同夠為："s = 3*(a+2*(c))"。

以上就是這道題目的內涵了。

總結（gpt4）

將字符串解碼問題與離散數學中的概念聯系起來，這是一種非常有趣的視角。確實，字符串解碼可以看作是對特定運算符（如拼接和重復）的遞歸運算。這種運算滿足一定的結合律，類似于群論中的一些運算屬性，盡管這里的操作并不構成嚴格數學意義上的群，因為群需要滿足閉合性、結合律、單位元存在以及每個元素存在逆元等條件。

提供的 C++ 代碼示例有效地實現了字符串解碼的功能，這里使用了兩個棧：一個存儲重復的次數（counts），另一個存儲到目前為止解析的字符串（strings）。這種方法非常適合處理嵌套的解碼結構。

深入理解：

每當遇到 '[' 時，把當前解析到的重復次數和字符串推入各自的棧中，并重置這些變量準備解析括號內的內容。當遇到 ']' 時，從棧中彈出最近的字符串和重復次數，并將解析到的字符串重復相應的次數，再與之前暫存的字符串拼接。

操作符和操作數的對應關系

• 操作數：字符串和整數（重復次數）
• 操作：兩種基本操作
  • int[string]：將字符串重復指定的次數
  • stringstring：將兩個字符串拼接起來

代碼確實很好地模擬了這一過程，但要注意一點細節上的問題：在字符串解碼結束后，如果主字符串（currentStr）后面沒有更多的操作，它將直接返回。這種情況下，代碼已經正確處理了所有情況。