LeetCode 394：字符串解碼

今天的題目來(lái)源于 LeetCode 第 394 號(hào)問題：字符串編碼，難度為「中等」，根據(jù)評(píng)論區(qū)的反饋，近期華為面試、字節(jié)面試都出現(xiàn)過。

一、題目描述

給定一個(gè)經(jīng)過編碼的字符串，返回它解碼后的字符串。

編碼規(guī)則為:k[encoded_string]，表示其中方括號(hào)內(nèi)部的encoded_string正好重復(fù)k次。注意k保證為正整數(shù)。

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

此外，你可以認(rèn)為原始數(shù)據(jù)不包含數(shù)字，所有的數(shù)字只表示重復(fù)的次數(shù)k，例如不會(huì)出現(xiàn)像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由小寫英文字母、數(shù)字和方括號(hào)'[]'組成
• s保證是一個(gè)有效的輸入。
• s中所有整數(shù)的取值范圍為[1, 300]

二、題目解析

注意示例 2 ，可以發(fā)現(xiàn)字符串中存在括號(hào)內(nèi)有嵌套括號(hào)的情況，這個(gè)時(shí)候，只有先把內(nèi)層括號(hào)解碼成功，才能再去解碼外層括號(hào)。

也就意味著后面訪問的括號(hào)比前面訪問的括號(hào)還更早的進(jìn)行處理，與棧的先入后出特點(diǎn)對(duì)應(yīng)。

所以，本題使用棧來(lái)處理。

具體操作如下：

1、構(gòu)建兩個(gè)棧，一個(gè)是數(shù)字棧numStack，在遍歷編碼字符串過程中記錄出現(xiàn)的數(shù)字；一個(gè)是字符串棧strStack，在遍歷編碼字符串過程中記錄出現(xiàn)的字符串。

2、初始化兩個(gè)變量，一個(gè)是digit，用來(lái)記錄訪問到字符串之前出現(xiàn)的數(shù)字；一個(gè)是res，在訪問編碼字符串的過程中，把得到的結(jié)果存放到 res 中。

3、接下來(lái)，開始從頭到尾訪問編碼字符串，在訪問過程中，字符會(huì)出現(xiàn) 4 種情況。

4、如果是數(shù)字，需要把字符轉(zhuǎn)成整型數(shù)字，然后更新到digit上，代表后續(xù)的字符串需要重復(fù)digit次。

5、如果是字符，說(shuō)明它就出現(xiàn)一次，可以直接存放到 res 中。

6、如果是"[" ，這個(gè)時(shí)候出現(xiàn)了嵌套的內(nèi)層編碼字符串，而外層的解碼需要等待內(nèi)層解碼的結(jié)果，那么之前已經(jīng)掃描的字符需要存放起來(lái)，等到內(nèi)層解碼之后再重新使用。

7、如果是"]" ，此時(shí)，內(nèi)層解碼已經(jīng)有結(jié)果，需要把它和前面的字符串進(jìn)行拼接。

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

9、最后返回 res 就行。

三、參考代碼

1、Java 代碼

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

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

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

//在訪問編碼字符串的過程中，用來(lái)記錄訪問到字符串之前出現(xiàn)的數(shù)字，一開始為0
intdigit=0;

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

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

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

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

//先將字符轉(zhuǎn)成整型數(shù)字ch-‘0’
//補(bǔ)充知識(shí)：將字符'0'-'9'轉(zhuǎn)換為數(shù)字，只需將字符變量減去'0'就行
//因?yàn)樽址蛿?shù)字在內(nèi)存里都是以ASCII碼形式存儲(chǔ)的
//減去'0'，其實(shí)就是減去字符'0'的ASCII碼，而字符'0'的ASCII碼是30
//所以減去'0'也就是減去30，然后就可以得到字符對(duì)應(yīng)的數(shù)字了。
intnum=ch-'0';

//再將這個(gè)數(shù)字和前面存儲(chǔ)的數(shù)字進(jìn)行組合
//1和2組成數(shù)字12，也就是1*10+2=12
//12和3組成數(shù)字123，也就是12*10+3=123
digit=digit*10+num;

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

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

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

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

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

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

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

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

//此時(shí)，內(nèi)層解碼已經(jīng)有結(jié)果，需要把它和前面的字符串進(jìn)行拼接

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

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

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

//再把此時(shí)得到的結(jié)果賦值給res
res=outString;
}
}

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

2、C++ 代碼

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

//創(chuàng)建字符棧，在遍歷編碼字符串過程中記錄出現(xiàn)的字符串
stack<string>strStack;

//在訪問編碼字符串的過程中，用來(lái)記錄訪問到字符串之前出現(xiàn)的數(shù)字，一開始為0
intdigit=0;

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

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

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

//先將字符轉(zhuǎn)成整型數(shù)字ch-‘0’
//補(bǔ)充知識(shí)：將字符'0'-'9'轉(zhuǎn)換為數(shù)字，只需將字符變量減去'0'就行
//因?yàn)樽址蛿?shù)字在內(nèi)存里都是以ASCII碼形式存儲(chǔ)的
//減去'0'，其實(shí)就是減去字符'0'的ASCII碼，而字符'0'的ASCII碼是30
//所以減去'0'也就是減去30，然后就可以得到字符對(duì)應(yīng)的數(shù)字了。
intnum=ch-'0';

//再將這個(gè)數(shù)字和前面存儲(chǔ)的數(shù)字進(jìn)行組合
//1和2組成數(shù)字12，也就是1*10+2=12
//12和3組成數(shù)字123，也就是12*10+3=123
digit=digit*10+num;

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

//說(shuō)明它就出現(xiàn)一次，可以直接存放到res中
res+=ch;

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

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

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

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

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

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

//此時(shí)，內(nèi)層解碼已經(jīng)有結(jié)果，需要把它和前面的字符串進(jìn)行拼接

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

numStack.pop();

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

strStack.pop();

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

//再把此時(shí)得到的結(jié)果賦值給res
res=outString;
}
}

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

3、Python 代碼

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

#創(chuàng)建字符棧，在遍歷編碼字符串過程中記錄出現(xiàn)的字符串
strStack=[]

#在訪問編碼字符串的過程中，用來(lái)記錄訪問到字符串之前出現(xiàn)的數(shù)字，一開始為0
digit=0

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

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

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

#先將字符轉(zhuǎn)成整型數(shù)字ch-‘0’
#補(bǔ)充知識(shí)：將字符'0'-'9'轉(zhuǎn)換為數(shù)字，只需將字符變量減去'0'就行
#因?yàn)樽址蛿?shù)字在內(nèi)存里都是以ASCII碼形式存儲(chǔ)的
#減去'0'，其實(shí)就是減去字符'0'的ASCII碼，而字符'0'的ASCII碼是30
#所以減去'0'也就是減去30，然后就可以得到字符對(duì)應(yīng)的數(shù)字了。
num=int(ch)

#再將這個(gè)數(shù)字和前面存儲(chǔ)的數(shù)字進(jìn)行組合
#1和2組成數(shù)字12，也就是1*10+2=12
#12和3組成數(shù)字123，也就是12*10+3=123
digit=digit*10+num

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

#說(shuō)明它就出現(xiàn)一次，可以直接存放到res中
res+=ch

#3、如果是"["
#出現(xiàn)了嵌套的內(nèi)層編碼字符串，而外層的解碼需要等待內(nèi)層解碼的結(jié)果
#那么之前已經(jīng)掃描的字符需要存放起來(lái)，等到內(nèi)層解碼之后再重新使用
elifch=='[':

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

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

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

#res重新初始化
res=""

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

#此時(shí)，內(nèi)層解碼已經(jīng)有結(jié)果，需要把它和前面的字符串進(jìn)行拼接

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

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

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


#再把此時(shí)得到的結(jié)果賦值給res
res=outString

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

四、復(fù)雜度分析

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