394. Decode String
two stack
time: O(n)
space: O(s1+s2), stack spaceuse this
class Solution {
public String decodeString(String s) {
Deque<String> strStack = new ArrayDeque<>();
Deque<Integer> numStack = new ArrayDeque<>();
StringBuilder cur = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (Character.isDigit(s.charAt(i))) {
int i0 = i;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
i++;
}
int num = Integer.valueOf(s.substring(i0, i));
numStack.push(num);
strStack.push(cur.toString());
cur = new StringBuilder();
} else if (s.charAt(i) == ']') {
int repeat = numStack.pop();
String temp = cur.toString();
for (int j = 0; j < repeat-1; j++) {
cur.append(temp);
}
cur = new StringBuilder(strStack.pop() + cur);
} else if (Character.isLetter(s.charAt(i))) {
cur.append(s.charAt(i));
}
}
return cur.toString();
}
}
/*
number: add number to number, cur str stack
1. number add to num stack, ๅ ็บ num ๅพ้ขๅฐฑๆฏ [, so add cur to str stack too, clear cur
2. char: add to cur
3. ้ๅฐ ], num ๅบๆฐ, str ๅบ็ซ, num*str => set to cur
aaa
3 ""
num. str
cur aaa -> ""
2
num. str
cur aaabcbc => ans
*//*
"3[a2[c]]"
countStack: 3 โ 2
resStack: "" โ a
res "" โ a โ "" c
meets ]
sb(a) + cc โ res = acc
meets ]
countStack: 3
resStack: ""
res acc
sb("") + 3*acc
res = accaccacc
1. number โ push countStack โ number push
2. '[' โ push resStack โ when '[', push res into it
1. char: add char
1. ']' โ pop
time: O(n)
space: O(s1+s2), stack space
*/
class Solution {
public String decodeString(String s) {
Deque<String> resStack = new ArrayDeque<>();
Deque<Integer> numStack = new ArrayDeque<>();
int i = 0;
StringBuilder res = new StringBuilder();
while (i < s.length()) {
if (Character.isDigit(s.charAt(i))) {
int num = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
num = num*10 + (s.charAt(i) - '0');
i++; // ๆๅพๆๅฐไธไธไฝ, ไนๅฐฑๆฏๅคๅ ไบไธๆฌก
}
numStack.push(num);
i--; // ๅคๅฑคๆๅi++, ๆ้่ฆ i--
} else if (s.charAt(i) == '[') {
resStack.push(res.toString());
res = new StringBuilder();
} else if (s.charAt(i) == ']') {
StringBuilder temp = new StringBuilder(resStack.pop());
int times = numStack.pop();
for (int j = 0; j < times; j++) {
temp.append(res);
}
res = temp;
} else {
res.append(s.charAt(i));
}
i++;
}
return res.toString();
}
}
/*
2 stack
d3[a]2[bc]d
3
numStack
when [, push to resStack
resstack
res+=letter
res = d
3
numStack
[
res = ""
d 3
resstack numStack
res = "a"
d 3
resstack numStack
]
res = "a"
d 3
resstack numStack
d3[a]2[bc]d
res = bc
daaa 2
resstack numStack
res = daaabcbcd
*/one stack
class Solution {
public String decodeString(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ']') {
List<Character> list = new ArrayList<>();
while (stack.peek() != '[') {
list.add(stack.pop());
}
stack.pop(); // [
int base = 1;
int k = 0;
while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
k += (stack.pop() - '0')*base;
base *= 10;
}
while (k != 0) {
for (int j = list.size()-1; j >= 0; j--) {
stack.push(list.get(j));
}
k--;
}
} else {
stack.push(s.charAt(i));
}
}
StringBuilder res = new StringBuilder();
while(!stack.isEmpty()) {
res.append(stack.pop());
}
return res.reverse().toString();
}
}
/*
3[a2[c]]
c
[
2
a
[
3
*/recursion
T: O(k*n), k is call dfs times, n is String length
S: O(n)
class Solution {
public String decodeString(String s) {
return dfs(s, 0)[0];
}
private String[] dfs(String s, int i) {
StringBuilder res = new StringBuilder();
int num = 0;
while(i < s.length()) {
if(Character.isDigit(s.charAt(i))) {
num = num * 10 + (s.charAt(i) - '0');
} else if(s.charAt(i) == '[') { // when [, call dfs(s, i+1) get str in [ str ]
String[] tmp = dfs(s, i + 1);
i = Integer.parseInt(tmp[0]);
for (int j = 0; j < num; j++) { // multi str, num needs set back to 0
res.append(tmp[1]);
}
num = 0;
} else if(s.charAt(i) == ']') { // when end, return String
return new String[] { String.valueOf(i), res.toString() };
} else { // letter, add
res.append(s.charAt(i));
}
i++;
}
return new String[] { res.toString() };
}
}
/*
d3[a2[c]]d
/
a2[c]
/
c
so when back, we can deal with number and decoded String
=> 2c => cc
=> acc
=> 3acc
=> daccaccaccd
*/or i as global variable
class Solution {
int i = 0;
public String decodeString(String s) {
return dfs(s);
}
private String dfs(String s) {
StringBuilder res = new StringBuilder();
int num = 0;
while(i < s.length()) {
if(Character.isDigit(s.charAt(i))) {
num = num * 10 + (s.charAt(i) - '0');
} else if(s.charAt(i) == '[') { // when [, call dfs(s, i+1) get str in [ str ]
i++;
String tmp = dfs(s);
for (int j = 0; j < num; j++) { // multi str, num needs set back to 0
res.append(tmp);
}
num = 0;
} else if(s.charAt(i) == ']') { // when end, return String
return res.toString();
} else { // letter, add
res.append(s.charAt(i));
}
i++;
}
return res.toString();
}
}Last updated
