394. 字符串解码

方法1：利用栈先进后出原则（模拟递归）

• digit = [] ###存放数字
• letter = [] ###存放数字前面的字母串
• res = ‘’ ###解码结果。在遍历过程中，也会临时存放字母串
  • 遇到左括号时，根据res更新letter，并清空res
  • 遇到右括号时，更新res

class Solution:
    def decodeString(self, s: str) -> str:
        digit = []   ###存放数字
        letter = []  ###存放数字前面的字母串
        res = ''     ###左括号后面的字母串
        number = 0   ###数字
        for i in s:
            if '0'<=i<='9':
                number = number*10+int(i)
            elif i=='[':
                digit.append(number)  ###当遇见左括号的时候数字结束，这个很关键
                letter.append(res)###遇见左括号的时候数字前面的字符串也存入栈
                number = 0 ###置零
                res = ''   ###置空
            elif i==']':   ###当遇见右括号取出数字前面的字母串，数字，然后数字乘以当前字符串
                a = digit.pop()
                b = letter.pop()
                res = b+a*res
            else:
                res += i ###当前数字后面的字母串
        return res

方法2：递归函数

• 将 [ 和 ] 分别作为递归的开启与终止条件。
• 明确递归函数的功能（不要跳进递归函数内）：decoding(s, index)返回字符串s中，以index下标开始的后面的子字符串解码后的结果。
  • 当's[i]=='['，进入递归函数，并接受返回值
  • 当 s[i]==']'，跳出此次递归

类似的题目有224.基本计算器

//#include <bits/stdc++.h>
//using namespace std;
class Solution {
public:
    int idx = 0; // 一个全局变量记录当前遍历的位置
    string decodeString(string s) {
        string res = ""; // 记录结果
        int num = 0; // 记录字符（串）前面的次数
        string tmp = ""; // 记录字符（串）
        while (idx < s.size()) {
            char c = s[idx++]; // 得到当前的字符，并且让索引+1
            if (isdigit(c)) { // 如果数字，则进行更新
                num = 10 * num + (c - '0');
            }
            if (c == '[') { // 如果是[ ，则进入递归
//                得到[后面的结果（相信递归函数能返回我需要的结果）
                tmp = decodeString(s);
                while (num--) { // 把这个结果添加到res中
                    res += tmp;
                }
                num = 0;
                tmp = "";
            }
//            如果是字母，则添加到res中
            if (isalpha(c)) { 
                res += c;
            }
            if (c == ']') break; // 如果是],则跳出递归函数
        }
        return res;
    }
};

//int main() {
////    string s = "3[a]2[bc]";
//    string s = "a2[x]";
//    Solution so;
//    cout << so.decodeString(s); // "aaabcbc"
//}

class Solution:
    def decodeString(self, s) :
        def decoding(s, index) :
            # num储存当前遍历到的数字
            # res储存当前遍历到的字符串
            num = ""
            res = ""

            # 遍历字符串
            while index < len(s):
                # 读取当前字符串
                current = s[index]
                # index表示当前字符的索引

                # 如果是数字，添加到num
                if current.isdigit():
                    num += current
                # 如果是字母，添加到res
                if current.isalpha():
                    res += current
                # 如果是"["，进入下一层递归并返回下一状态的res
                # 返回的res与当前状态下的num相乘，并添加到当前的res
                if current == "[":
                    # temp表示解码后的结果，index表示下标
                    temp, index = decoding(s, index+1)
                    res += int(num) * temp
                    num = ""
                # 如果是"]",返回这一状态的res与index
                if current == "]":
                    # 返回这一状态的res与index
                    return res, index
                # 下标右移，继续下一次循环
                index += 1

            # 遍历完所有字符串，返回res
            return res

        # 开始递归，index初始为0  
        return decoding(s, 0)

2020秋招腾讯后台笔试题（一）

该题的思路同上，也是利用栈

• |就相当于上题的[的功能。
• 而[ 在本题没用，删除掉[（或者直接跳过）即可
  • C++删除[：s.erase(remove(s.begin(),s.end(),'['),s.end());
  • python删除[：s=s.replace('[','')

def decodeString(s) :
    # 删除掉'['字符
    s=s.replace('[','')
    digit = []   ###存放数字
    letter = []  ###存放数字前面的字母串
    res = ''     ###左括号后面的字母串
    number = 0   ###数字
    for i in s:
        if '0'<=i<='9':
            number = number*10+int(i)
        elif i=='|':
            digit.append(number)  ###当遇见左括号的时候数字结束，这个很关键
            letter.append(res)###遇见左括号的时候数字前面的字符串也存入栈
            number = 0 ###置零
            res = ''   ###置空
        elif i==']':   ###当遇见右括号取出数字前面的字母串，数字，然后数字乘以当前字符串
            a = digit.pop()
            b = letter.pop()
            res = b+a*res
        else:
            res += i ###当前数字后面的字母串
    return res
a=input()
print(decodeString(a))

//#include <bits/stdc++.h>
//using namespace std;
class Solution {
public:
    int idx = 0; // 一个全局变量记录当前遍历的位置
    string decodeString(string s) {
        string res = "";
        int num = 0;
        string tmp = "";
        while (idx < s.size()) {
            char c = s[idx++]; // 得到当前的字符，并且让索引+1
            if (isdigit(c)) { // 如果数字，则进行更新
                num = 10 * num + (c - '0');
            }
            if (c == '|') { // 如果是[ ，则进入索引
//                得到[后面的结果（相信递归函数能返回我需要的结果）
                tmp = decodeString(s);
                while (num--) { // 把这个结果添加到res中
                    res += tmp;
                }
                num = 0;
                tmp = "";
            }
//            如果是字母，则添加到res中
            if (isalpha(c)) {
                res += c;
            }
            if (c == ']') break; // 如果是],则退出递归函数
        }
        return res;
    }
};

//int main() {
//    string s = "HG[3|B[2|CA]]F";
//    Solution so;
//    cout << so.decodeString(s); // "aaabcbc"
//}