forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathExpression Expand.java
More file actions
148 lines (133 loc) · 4.87 KB
/
Expression Expand.java
File metadata and controls
148 lines (133 loc) · 4.87 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
M
1520800825
tags: Divide and Conquer, Stack, DFS
#### DFS
- 与Stack时需要考虑的一些function类似. 特别之处: **检查[ ]的结尾**
- 因为DFS时候, 括号里的substring会被保留着进入下一个level, 所以我们在base level要keep track of substring.
- 用int paren 来track 括号的开合, 当paren再次==0的时候 找到closure ']'
#### Stack
- Stack存 [ ] 里面的内容, detect 括号开头结尾: 结尾时process inner string
- 有很多需要注意的细节才能做对:
- Stack<Object> 也可以用, 每个地方要注意 cast. 存进去的需要是Object: String, Integer
- 几个 type check: instanceof String, Character.isDigit(x), Integer.valueOf(int num)
- 出结果时候, 不能轻易 sb.reverse().toString(): sb.reverse() 翻转了整个连在一起的string, 错.
- 用另一个Stack<String>作为buffer, 先把stack里面的内容倒出来 (pure), 但是每个item里面顺序不变.
- 最后再从buffer里面倒进StringBuffer.
```
/*
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.
*/
/*
Thoughts:
Can DFS. Also, use stack to hold all inner bucket.
In the original string, block of string is separated by #[ ].
Can use stack to hold 2 piece of information:
1. # where the str repeats, and it also marks the start of the string
2. Store each char of the string itself
3. Once flatten the inner str, repeat the str # times and add back to stack
As we iterate over the string
- detect '[' to determine the time to add start marker #.
- detect ']' when it's time to retrieve the # and str, save results
Important: use Stack to hold generic Object!
*/
public class Solution {
/**
* @param s: an expression includes numbers, letters and brackets
* @return: a string
*/
public String expressionExpand(String s) {
if (s == null || s.length() == 0) {
return "";
}
Stack<Object> stack = new Stack<>();
int number = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
number = number * 10 + (c - '0');
} else if (c == '[') {
stack.push(Integer.valueOf(number));
number = 0;
} else if (c == ']') {
String str = popStack(stack);
Integer num = (Integer) stack.pop();
for (int i = 0; i < num; i++) {
stack.push(str);
}
} else {
stack.push(String.valueOf(c));
}
}
return popStack(stack);
}
private String popStack(Stack<Object> stack) {
StringBuffer sb = new StringBuffer();
Stack<String> buffer = new Stack<>();
while (!stack.isEmpty() && (stack.peek() instanceof String)) {
buffer.push((String) stack.pop());
}
while (!buffer.isEmpty()) {
sb.append(buffer.pop());
}
return sb.toString();
}
}
/*
Thoughts:
DFS, process inner string each time.
Use "#[" as detection.
Important:
1. Finding the closure of ']' is tricky: need to track the parentheses
2. Until we find the closure ']', keep track of the un-flatten substring for dfs to use
*/
public class Solution {
/**
* @param s: an expression includes numbers, letters and brackets
* @return: a string
*/
public String expressionExpand(String s) {
if (s == null || s.length() == 0) {
return "";
}
StringBuffer sb = new StringBuffer();
String substring = "";
int number = 0;
int paren = 0; // parentheses tracker
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '[') {
if (paren > 0) { // if paren == 0, it indicates the outside 1st '[', no need to record
substring += c;
}
paren++;
} else if (c == ']') {
paren--;
if (paren == 0) {
String innerString = expressionExpand(substring);
for (int num = 0; num < number; num++) {
sb.append(innerString);
}
number = 0;
substring = "";
} else {
substring += c;
}
} else if (Character.isDigit(c)) {
if (paren == 0) {
number = number * 10 + (c - '0');
} else {
substring += c;
}
} else {
if (paren == 0) {
sb.append(String.valueOf(c));
} else {
substring += c;
}
}
}
return sb.toString();
}
}
```