[LeetCode] 394. Decode String

轉自LeetCode

Given an encoded string, return it's decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that kis guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

<Solution>

看到有對稱形式，然後又可以內嵌

就可以往 stack 的方向去思考

想法如下

• 準備兩個 stack，一個存數字，一個存字串
• 遇到 ' [ '，就將目前的數字和字串 push 到 stack
• 遇到 ' ] '，就把當前的字串，重複 number stack 上 top 的次數，並接到 string stack 上的top

c++

kotlin