今天的題目來源于 LeetCode 第 394 號問題：字符串編碼，難度為「中等」，根據評論區的反饋，近期華為面試、字節面試都出現過。

一、題目描述

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

編碼規則為:k[encoded_string]，表示其中方括號內部的encoded_string正好重復k次。注意k保證為正整數。

你可以認為輸入字符串總是有效的；輸入字符串中沒有額外的空格，且輸入的方括號總是符合格式要求的。

此外，你可以認為原始數據不包含數字，所有的數字只表示重復的次數k，例如不會出現像3a或2[4]的輸入。

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

提示：

• 1 <= s.length <= 30
• s由小寫英文字母、數字和方括號'[]'組成
• s保證是一個有效的輸入。
• s中所有整數的取值范圍為[1, 300]

二、題目解析

注意示例 2 ，可以發現字符串中存在括號內有嵌套括號的情況，這個時候，只有先把內層括號解碼成功，才能再去解碼外層括號。

也就意味著后面訪問的括號比前面訪問的括號還更早的進行處理，與棧的先入后出特點對應。

所以，本題使用棧來處理。

具體操作如下：

1、構建兩個棧，一個是數字棧numStack，在遍歷編碼字符串過程中記錄出現的數字；一個是字符串棧strStack，在遍歷編碼字符串過程中記錄出現的字符串。

2、初始化兩個變量，一個是digit，用來記錄訪問到字符串之前出現的數字；一個是res，在訪問編碼字符串的過程中，把得到的結果存放到 res 中。

3、接下來，開始從頭到尾訪問編碼字符串，在訪問過程中，字符會出現 4 種情況。

4、如果是數字，需要把字符轉成整型數字，然后更新到digit上，代表后續的字符串需要重復digit次。

5、如果是字符，說明它就出現一次，可以直接存放到 res 中。

6、如果是"[" ，這個時候出現了嵌套的內層編碼字符串，而外層的解碼需要等待內層解碼的結果，那么之前已經掃描的字符需要存放起來，等到內層解碼之后再重新使用。

7、如果是"]" ，此時，內層解碼已經有結果，需要把它和前面的字符串進行拼接。

8、拼接的方式就是先通過 numsStack 的棧頂元素獲取重復的次數，再通過 strStack 的棧頂元素獲取前面的字符串。

9、最后返回 res 就行。

三、參考代碼

1、Java 代碼

//登錄AlgoMooc官網獲取更多算法圖解
//https://www.algomooc.com
//作者：程序員吳師兄
//代碼有看不懂的地方一定要私聊咨詢吳師兄呀
//字符串解碼(LeetCode394)//leetcode.cn/problems/decode-string/
classSolution{
publicStringdecodeString(Strings){

//創建數字棧，在遍歷編碼字符串過程中記錄出現的數字
DequenumStack=newLinkedList<>();

//創建字符棧，在遍歷編碼字符串過程中記錄出現的字符串
DequestrStack=newLinkedList<>();

//在訪問編碼字符串的過程中，用來記錄訪問到字符串之前出現的數字，一開始為0
intdigit=0;

//在訪問編碼字符串的過程中，把得到的結果存放到res中
StringBuilderres=newStringBuilder();

//從頭到尾遍歷編碼字符串
for(inti=0;i//在遍歷過程中，字符會出現4種情況

//先獲取此時訪問的字符
charch=s.charAt(i);

//1、如果是數字，需要把字符轉成整型數字
//注意數字不一定是1位，有可能是多位
//比如123a，在字母a的前面出現了123，表示a重復出現123次
//那么一開始ch為1，當訪問到ch為2的時候，1和2要組成數字12
//再出現3，12和3組成數字123
if(Character.isDigit(ch)){

//先將字符轉成整型數字ch-‘0’
//補充知識：將字符'0'-'9'轉換為數字，只需將字符變量減去'0'就行
//因為字符和數字在內存里都是以ASCII碼形式存儲的
//減去'0'，其實就是減去字符'0'的ASCII碼，而字符'0'的ASCII碼是30
//所以減去'0'也就是減去30，然后就可以得到字符對應的數字了。
intnum=ch-'0';

//再將這個數字和前面存儲的數字進行組合
//1和2組成數字12，也就是1*10+2=12
//12和3組成數字123，也就是12*10+3=123
digit=digit*10+num;

//2、如果是字符
}elseif((ch>='a'&&ch<=?'z')){

//說明它就出現一次，可以直接存放到res中
res.append(ch);

//3、如果是"["
//出現了嵌套的內層編碼字符串，而外層的解碼需要等待內層解碼的結果
//那么之前已經掃描的字符需要存放起來，等到內層解碼之后再重新使用
}elseif(ch=='['){

//把數字存放到數字棧
numStack.push(digit);

//把外層的解碼字符串存放到字符串棧
strStack.push(res);

//開始新的一輪解碼
//于是，digit歸零
digit=0;

//res重新初始化
res=newStringBuilder();

//4、如果是"]"
}elseif(ch==']'){

//此時，內層解碼已經有結果，需要把它和前面的字符串進行拼接

//第一步，先去查看內層解碼的字符串需要被重復輸出幾次
//比如e3[abc]，比如內層解碼結果abc需要輸出3次
//通過數字棧提取出次數
intcount=numStack.poll();

//第二步，通過字符串棧提取出之前的解碼字符串
StringBuilderoutString=strStack.poll();

//第三步，不斷的把內層解碼的字符串拼接起來
for(intj=0;j//拼接到outString后面，拼接count次
outString.append(res.toString());
}

//再把此時得到的結果賦值給res
res=outString;
}
}

//返回解碼成功的字符串
returnres.toString();
}
}

2、C++ 代碼

classSolution{
public:
stringdecodeString(strings){
//創建數字棧，在遍歷編碼字符串過程中記錄出現的數字
stack<int>numStack;

//創建字符棧，在遍歷編碼字符串過程中記錄出現的字符串
stack<string>strStack;

//在訪問編碼字符串的過程中，用來記錄訪問到字符串之前出現的數字，一開始為0
intdigit=0;

//在訪問編碼字符串的過程中，把得到的結果存放到res中
stringres;

//從頭到尾遍歷編碼字符串
for(inti=0;i//在遍歷過程中，字符會出現4種情況

//先獲取此時訪問的字符
charch=s[i];
//1、如果是數字，需要把字符轉成整型數字
//注意數字不一定是1位，有可能是多位
//比如123a，在字母a的前面出現了123，表示a重復出現123次
//那么一開始ch為1，當訪問到ch為2的時候，1和2要組成數字12
//再出現3，12和3組成數字123
if(ch>='0'&&ch<='9'){

//先將字符轉成整型數字ch-‘0’
//補充知識：將字符'0'-'9'轉換為數字，只需將字符變量減去'0'就行
//因為字符和數字在內存里都是以ASCII碼形式存儲的
//減去'0'，其實就是減去字符'0'的ASCII碼，而字符'0'的ASCII碼是30
//所以減去'0'也就是減去30，然后就可以得到字符對應的數字了。
intnum=ch-'0';

//再將這個數字和前面存儲的數字進行組合
//1和2組成數字12，也就是1*10+2=12
//12和3組成數字123，也就是12*10+3=123
digit=digit*10+num;

//2、如果是字符
}elseif((ch>='a'&&ch<=?'z')){

//說明它就出現一次，可以直接存放到res中
res+=ch;

//3、如果是"["
//出現了嵌套的內層編碼字符串，而外層的解碼需要等待內層解碼的結果
//那么之前已經掃描的字符需要存放起來，等到內層解碼之后再重新使用
}elseif(ch=='['){

//把數字存放到數字棧
numStack.push(digit);

//把外層的解碼字符串存放到字符串棧
strStack.push(res);

//開始新的一輪解碼
//于是，digit歸零
digit=0;

//res重新初始化
res="";

//4、如果是"]"
}elseif(ch==']'){

//此時，內層解碼已經有結果，需要把它和前面的字符串進行拼接

//第一步，先去查看內層解碼的字符串需要被重復輸出幾次
//比如e3[abc]，比如內層解碼結果abc需要輸出3次
//通過數字棧提取出次數
intcount=numStack.top();

numStack.pop();

//第二步，通過字符串棧提取出之前的解碼字符串
stringoutString=strStack.top();

strStack.pop();

//第三步，不斷的把內層解碼的字符串拼接起來
for(intj=0;j//拼接到outString后面，拼接count次
outString+=res;
}

//再把此時得到的結果賦值給res
res=outString;
}
}

//返回解碼成功的字符串
returnres;
}
};

3、Python 代碼

classSolution:
defdecodeString(self,s:str)->str:
#創建數字棧，在遍歷編碼字符串過程中記錄出現的數字
numStack=[]

#創建字符棧，在遍歷編碼字符串過程中記錄出現的字符串
strStack=[]

#在訪問編碼字符串的過程中，用來記錄訪問到字符串之前出現的數字，一開始為0
digit=0

#在訪問編碼字符串的過程中，把得到的結果存放到res中
res=""

#從頭到尾遍歷編碼字符串
forchins:

#在遍歷過程中，字符會出現4種情況
#先獲取此時訪問的字符
#1、如果是數字，需要把字符轉成整型數字
#注意數字不一定是1位，有可能是多位
#比如123a，在字母a的前面出現了123，表示a重復出現123次
#那么一開始ch為1，當訪問到ch為2的時候，1和2要組成數字12
#再出現3，12和3組成數字123
if'0'<=?ch?<=?'9':

#先將字符轉成整型數字ch-‘0’
#補充知識：將字符'0'-'9'轉換為數字，只需將字符變量減去'0'就行
#因為字符和數字在內存里都是以ASCII碼形式存儲的
#減去'0'，其實就是減去字符'0'的ASCII碼，而字符'0'的ASCII碼是30
#所以減去'0'也就是減去30，然后就可以得到字符對應的數字了。
num=int(ch)

#再將這個數字和前面存儲的數字進行組合
#1和2組成數字12，也就是1*10+2=12
#12和3組成數字123，也就是12*10+3=123
digit=digit*10+num

#2、如果是字符
elifch>='a'andch<=?'z':

#說明它就出現一次，可以直接存放到res中
res+=ch

#3、如果是"["
#出現了嵌套的內層編碼字符串，而外層的解碼需要等待內層解碼的結果
#那么之前已經掃描的字符需要存放起來，等到內層解碼之后再重新使用
elifch=='[':

#把數字存放到數字棧
numStack.append(digit)

#把外層的解碼字符串存放到字符串棧
strStack.append(res)

#開始新的一輪解碼
#于是，digit歸零
digit=0

#res重新初始化
res=""

#4、如果是"]"
elifch==']':

#此時，內層解碼已經有結果，需要把它和前面的字符串進行拼接

#第一步，先去查看內層解碼的字符串需要被重復輸出幾次
#比如e3[abc]，比如內層解碼結果abc需要輸出3次
#通過數字棧提取出次數
count=numStack.pop()

#第二步，通過字符串棧提取出之前的解碼字符串
outString=strStack.pop()

#第三步，不斷的把內層解碼的字符串拼接起來
forjinrange(0,count):
#拼接到outString后面，拼接count次
outString+=res


#再把此時得到的結果賦值給res
res=outString

#返回解碼成功的字符串
returnres

四、復雜度分析

• 時間復雜度 O(N)，一次遍歷s
• 空間復雜度 O(N)，輔助棧在極端情況下需要線性空間。