1+ // 394. 字符串解码
2+
3+
4+ /*
5+ 栈：（这种解法更容易理解）
6+ 1、把所有字符入栈，除了']'
7+ 2、从栈取出[]内的字符串
8+ 3、弹出'['，丢弃
9+ 4、从栈获取倍数数字
10+ 5、根据倍数把字母入栈
11+ 6、把栈里面所有的字母取出来，得到结果
12+ */
13+ class Solution {
14+ public String decodeString (String s ) {
15+ Stack <Character > stack = new Stack <>();
16+ for (char c : s .toCharArray ()) {
17+ if (c != ']' ) {
18+ stack .push (c );
19+ } else {
20+ StringBuilder sb = new StringBuilder ();
21+ while (!stack .isEmpty () && Character .isLetter (stack .peek ())) {
22+ sb .insert (0 , stack .pop ());
23+ }
24+ String sub = sb .toString ();
25+ stack .pop ();
26+ sb = new StringBuilder ();
27+ while (!stack .isEmpty () && Character .isDigit (stack .peek ())) {
28+ sb .insert (0 , stack .pop ());
29+ }
30+ int count = Integer .valueOf (sb .toString ());
31+ while (count > 0 ) {
32+ for (char ch : sub .toCharArray ()) {
33+ stack .push (ch );
34+ }
35+ count --;
36+ }
37+ }
38+ }
39+ StringBuilder res = new StringBuilder ();
40+ while (!stack .isEmpty ()) {
41+ res .insert (0 , stack .pop ());
42+ }
43+ return res .toString ();
44+ }
45+ }
46+
47+
48+ /*
49+ 栈：
50+ 1、外层的解码需要等待内层解码的结果。先扫描的字符还用不上，但不能忘了它们。我们准备由内到外，层层解决[]，需要保持对字符的记忆，于是用栈。
51+ 2、变量含义：
52+ kStack：存放每一层[]的倍数，遇到'['时入栈暂存，遇到']'时出栈计算当前层解码结果
53+ resStack：存放上一层[]的子串，遇到'['时入栈暂存，遇到']'时出栈与当前层解码结果拼接
54+ res：表示当前层[]的子串，最外层没有[]
55+ k：表示当前层[]的倍数
56+ temp：表示当前层[]的解码结果
57+ 2、入栈时机：遇到'['，意味着要开始解决内层的字符了，外层的数字和子串入栈暂存，并且变量归零用于内层继续计算
58+ 1）当遇到'['，已经扫描的数字就是遇到的[]的“倍数”，入栈暂存
59+ 2）当遇到'['，已经扫描的子串也入栈暂存，括号里的字符解码完后，再一起参与构建字符串
60+ 3、出栈时机：遇到']'，内层的字符串扫描完了，数字出栈构建新子串，旧子串出栈与新子串拼接得到最新结果
61+
62+ ========== 过程一 =========
63+ s = "abc3[a2[d]]ef"
64+ ↑
65+ k = 3
66+ res = "abc"
67+ stack = [(3, "abc")]
68+ ========== 过程二 =========
69+ s = "abc3[a2[d]]ef"
70+ ↑
71+ k = 2
72+ res = "a"
73+ stack = [(3, "abc"), (2, "a")]
74+ ========== 过程三 =========
75+ s = "abc3[a2[d]]ef"
76+ ↑
77+ k = 0
78+ res = "d"
79+ curk = 2
80+ oldres = "a"
81+ stack = [(3, "abc")]
82+ temp = curk * res = "dd"
83+ res = oldres + curk * res = "add"
84+ ========== 过程四 =========
85+ s = "abc3[a2[d]]ef"
86+ ↑
87+ k = 0
88+ res = "add"
89+ curk = 3
90+ oldres = "abc"
91+ stack = [(3, "abc")]
92+ temp = curk * res = "addaddadd"
93+ res = oldres + curk * res = "abcaddaddadd"
94+ ========== 过程五 =========
95+ s = "abc3[a2[d]]ef"
96+ ↑
97+ res = "abcaddaddaddef"
98+ */
99+ class Solution {
100+ public String decodeString (String s ) {
101+ Deque <Integer > kStack = new ArrayDeque <>();
102+ Deque <StringBuilder > resStack = new ArrayDeque <>();
103+ StringBuilder res = new StringBuilder ();
104+ int k = 0 ;
105+ for (char c : s .toCharArray ()) {
106+ if (c >= '0' && c <= '9' ) {
107+ k = k * 10 + (c - '0' );
108+ } else if (c == '[' ) {
109+ kStack .push (k );
110+ resStack .push (res );
111+ k = 0 ;
112+ res = new StringBuilder ();
113+ } else if (c == ']' ) {
114+ StringBuilder temp = new StringBuilder ();
115+ int kCur = kStack .pop ();
116+ for (int i = 0 ; i < kCur ; i ++) {
117+ temp .append (res );
118+ }
119+ res = resStack .pop ().append (temp );
120+ } else {
121+ res .append (c );
122+ }
123+ }
124+ return res .toString ();
125+ }
126+ }
0 commit comments