Title

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

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

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

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

示例:

s = “3[a]2[bc]”, 返回 “aaabcbc”.
s = “3[a2[c]]”, 返回 “accaccacc”.
s = “2[abc]3[cd]ef”, 返回 “abcabccdcdcdef”.

Solve

本題中可能出現(xiàn)括號嵌套的情況，比如 2[a2[bc]]，這種情況下我們可以先轉(zhuǎn)化成 2[abcbc]，在轉(zhuǎn)化成 abcbcabcbc。

我們可以把字母、數(shù)字和括號看成是獨立的 TOKEN，并用棧來維護這些 TOKEN。具體的做法是，遍歷這個棧：

• 如果當(dāng)前的字符為數(shù)位，解析出一個數(shù)字（連續(xù)的多個數(shù)位）并進棧
• 如果當(dāng)前的字符為字母或者左括號，直接進棧
• 如果當(dāng)前的字符為右括號，開始出棧，一直到左括號出棧，出棧序列反轉(zhuǎn)后拼接成一個字符串，此時取出棧頂?shù)臄?shù)字，就是這個字符串應(yīng)該出現(xiàn)的次數(shù)，我們根據(jù)這個次數(shù)和字符串構(gòu)造出新的字符串并進棧

重復(fù)如上操作，最終將棧中的元素按照從棧底到棧頂?shù)捻樞蚱唇悠饋?#xff0c;就得到了答案。注意：這里可以用不定長數(shù)組來模擬棧操作，方便從棧底向棧頂遍歷。

Code

class Solution:def decodeString(self, s: str) -> str:stack = []for index, value in enumerate(s):stack.append(value)if value == ']':for i in range(len(stack) - 2, -1, -1):if stack[i] == '[':string = stack[i + 1: len(stack) - 1]for j in range(i - 1, -1, -1):if j == 0 or not stack[j - 1].isdigit():num = int(''.join(stack[j:i]))stack = stack[:j]stack.extend(num * string)breakbreakreturn ''.join(stack)

總結(jié)

以上是生活随笔為你收集整理的394. Decode String的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。