Lintcode575 Decode String 题解

【题目描述】

Given an expression s includes numbers, letters and brackets. Number represents the number of repetitions inside the brackets(can be a string or another expression)．Please expand expression to be a string.

Example

s = abc3[a] return abcaaa

s = 3[abc] return abcabcabc

s = 4[ac]dy, return acacacacdy

s = 3[2[ad]3[pf]]xyz, return adadpfpfpfadadpfpfpfadadpfpfpfxyz

给出一个表达式 s，此表达式包括数字，字母以及方括号。在方括号前的数字表示方括号内容的重复次数(括号内的内容可以是字符串或另一个表达式)，请将这个表达式展开成一个字符串。

样例

S = abc3[a] 返回 abcaaa

S = 3[abc] 返回 abcabcabc

S = 4[ac]dy 返回 acacacacdy

S = 3[2[ad]3[pf]]xyz 返回 adadpfpfpfadadpfpfpfadadpfpfpfxyz

【题目链接】

www.lintcode.com/en/problem/decode-string/

【题目解析】

递归的思路

递归计算出括号最里面的字符串，依次再处理外面一层的字符串，每个单元内的字符串类似于一个结点，个数则为结点的个数。父结点则是将这些个数的字符串组合在一起，以此类推到跟结点，就是我们要求的结果。

迭代的思路

用两个栈来分别保存下单元中的个数，另一个则保存单元中的字符串，注意的是，要将最新的处理完后的字符串加入到栈中。一直加入，直到最后返回栈顶字符串则为所求结果。

【参考答案】

www.jiuzhang.com/solutions/decode-string/