【题目描述】
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/
【题目解析】
递归的思路
递归计算出括号最里面的字符串,依次再处理外面一层的字符串,每个单元内的字符串类似于一个结点,个数则为结点的个数。父结点则是将这些个数的字符串组合在一起,以此类推到跟结点,就是我们要求的结果。
迭代的思路
用两个栈来分别保存下单元中的个数,另一个则保存单元中的字符串,注意的是,要将最新的处理完后的字符串加入到栈中。一直加入,直到最后返回栈顶字符串则为所求结果。
【参考答案】