leetcode394：字符串解码

题目链接

leetcode

题目描述

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

C++ 代码

#include <iostream>
#include <string>
#include <stack>
using namespace std;

/*
    把字母、数字和括号看成是独立的 TOKEN，用栈来维护这些 TOKEN。
    注意：本题中可能出现括号嵌套的情况
    
    具体做法：遍历这个栈
        若当前字符为数字，则拼接出完整的数字；
        若当前字符为左括号，则数字和字母都进栈；
        若当前字符为字母，则拼接出完整的字符串；
        若当前字符为右括号，则字母和数字都出栈，并根据字符串和次数拼接出新的字符串。
    重复如上操作，将栈中的元素按照从栈底到栈顶的顺序拼接，就得到了答案。

    时间复杂度：O(n)
        假设解码后得出的字符串长度为 n，除了遍历一次原字符串 s，
        还需要将解码后的字符串中的每个字符都入栈，最终拼接进答案，
        故渐进时间复杂度为 O(n+∣n∣)，即 O(n)。
    空间复杂度：O(n)
        用栈维护 TOKEN，栈的总大小等于字符串长度，故渐进空间复杂度为 O(n)。
*/
class Solution {
public:
    string decodeString(string s) {
        string strNum = "", strChar = "";
        stack<string> stk;
        for (const char c : s) {
            if (isdigit(c)) {
                // 若当前字符为数字，则拼接出完整的数字。
                strNum += c;
            } else if (c == '[') {
                // 若当前字符为左括号，则数字和字母都进栈。
                stk.push(strNum);
                strNum = "";
                stk.push(strChar);
                strChar = "";
            } else if (isalpha(c)) {
                // 若当前字符为字母，则拼接出完整的字符串。
                strChar += c;
            } else {
                // 若当前字符为右括号，则字母和数字都出栈，并根据字符串和次数拼接出新的字符串。
                string chars = stk.top(); stk.pop();
                string times = stk.top(); stk.pop();
                int iTimes = atoi(times.c_str());
                for (int i = 0; i < iTimes; i ++) {
                    chars += strChar;
                }
                strChar = chars;
            }
        }

        return strChar;
    }
};

/*
    思路同上
*/
class Solution_1 {
public:
    string decodeString(string s) {
        stack<pair<string, int>> stk;
        string curStr = "";
        int curNum = 0;
        for (const char& ch : s) {
            if (isdigit(ch)) {
                curNum = curNum * 10 + (ch - '0');
            } else if (isalpha(ch)) {
                curStr += ch;
            } else if (ch == '[') {
                stk.push({curStr, curNum});
                curStr = "";
                curNum = 0;
            } else if (ch == ']') {
                auto top = stk.top(); stk.pop();
                // repeatString
                string repeatString;
                for (int i = 0; i < top.second; i ++) {
                    repeatString += curStr;
                }
                curStr = top.first + repeatString;
            }
        }

        return curStr;
    }
};

int main() {
    Solution solution;
    string input = "3[a]2[bc]";
    cout << "Decoded string: " << solution.decodeString(input) << endl; // 输出 "aaabcbc"

    return 0;
}

Golang 代码

package main

import (
	"fmt"
	"strings"
)

/*
   栈的使用：
       使用一个字符串栈来存储数字、字母和 [。
       遇到 ] 时，弹出字符串直到遇到 [，并将弹出的字符串反转拼接。
       弹出 [ 后，再弹出数字，将字符串重复指定次数。
       将重复后的字符串压入栈中。
   处理数字：
       数字可能有多位，因此需要连续读取直到遇到非数字字符。
   拼接结果：
       最终将栈中的所有字符串拼接起来，得到解码后的结果。

    时间复杂度：O(n)
        其中 n 是输入字符串的长度。
        每个字符最多被处理两次（一次入栈，一次出栈），因此时间复杂度为 O(n)。
    空间复杂度：O(n)
        使用了栈来存储中间结果，空间复杂度为 O(n)。
*/
// decodeString 解码字符串
func decodeString(s string) string {
    type stackElem struct {
		num int    // 重复次数
		str string // 累积字符串
	}
	stack := []stackElem{}
	currentNum := 0
	currentStr := ""

	for _, char := range s {
		switch {
		case char >= '0' && char <= '9':
			// 处理多位数：当前数字 = 当前数字×10 + 新数字
			currentNum = currentNum*10 + int(char - '0')
        case char >= 'a' && char <= 'z' || char >= 'A' && char <= 'Z':
			// 普通字符直接追加
			currentStr += string(char)
		case char == '[':
			// 入栈当前状态并重置
			stack = append(stack, stackElem{currentNum, currentStr})
			currentNum = 0
			currentStr = ""
		case char == ']':
			// 弹出栈顶元素并生成重复字符串
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			currentStr = top.str + strings.Repeat(currentStr, top.num)
		// default:
		// 	// 普通字符直接追加
		// 	currentStr += string(char)
		}
	}
	return currentStr
}

func main() {
	// 测试用例
	testCases := []struct {
		input    string
		expected string
	}{
		{"3[a]2[bc]", "aaabcbc"},
		{"3[a2[c]]", "accaccacc"},
		{"2[abc]3[cd]ef", "abcabccdcdcdef"},
		{"abc3[cd]xyz", "abccdcdcdxyz"},
	}

	for i, tc := range testCases {
		result := decodeString(tc.input)
		fmt.Printf("Test Case %d, Input: %q\n", i+1, tc.input)

		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %q, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %q, FAIL (Expected: %q)\n", i+1, result, tc.expected)
		}
	}
}