前往
大廳
主題

LeetCode - 394. Decode String 解題心得

Not In My Back Yard | 2022-06-09 12:00:01 | 巴幣 0 | 人氣 296

題目連結:


題目意譯:
給定一個加密的字串,回傳將其解密後的字串。

加密規則為:k[encoded_string],其中在中括號裡面的 encoded_string 將被重複恰好 k 次。注意,k 保證為一正整數。

你可以假設輸入字串保證合法、沒有多餘的空白、中括號之配對為合法的等等。除此之外,你還可以假設原始的資料並不包含數字,而數字只將用來代表這些重複次數 k。例如,不會有輸入像是 3a 或是 2[4] 等。

測試資料之生成滿足輸出的長度保證不超過 10 ^ 5。

限制:
1 ≦ s.length ≦ 30
s 由小寫英文字母、數字以及中括號 '[]' 所組成。
s 保證為一個合法的輸入。
s 中所有整數數值位於範圍 [1, 300]。



範例測資:
範例 1:
輸入: s = "3[a]2[bc]"
輸出: "aaabcbc"

範例 2:
輸入: s = "3[a2[c]]"
輸出: "accaccacc"

範例 3:
輸入: s = "2[abc]3[cd]ef"
輸出: "abcabccdcdcdef"


解題思維:
從範例輸入 2 可以看到中括號裡面可以再包著中括號。因此我們在掃過字串 s 時,碰到左中括號時就去找與其配對的右中括號(作法參見這題),然後遞迴把這兩個中括號中間的字串解密出來並重複左中括號前的整數次數即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作