forked from super30admin/DFS-2
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Problem2.java
133 lines (111 loc) · 3.81 KB
/
Problem2.java
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
// There are two approaches
// Did this code successfully run on Leetcode : yes
// Any problem you faced while coding this : no
import java.util.Stack;
import java.util.Collections;
// Your code here along with comments explaining your approach
// Approach 1: Using Stack
// Time Complexity : O(n * max(k))
// n: length of the String
// k: Multiplication factor
// Space Complexity : O(n)
// n: length of the String
class Problem2S1 {
/** Decode the string */
public String decodeString(String s) {
// edge case
if(s==null || s.length() ==0)
return s;
// Using string builder as we need to append many times
StringBuilder current = new StringBuilder();
StringBuilder number = new StringBuilder();
// Stack
Stack<StringBuilder> stringStack = new Stack<>();
Stack<Integer> numStack = new Stack<>();
// iterate all the characters
for(int i=0; i<s.length();i++){
char c = s.charAt(i);
// closing bracket then pop
if(c == ']'){
// first mutiply the current string by k factor(popped from numsStack)
String temp = String.join("", Collections.nCopies(numStack.pop(), current)); // gets n copies
// Pop from String stack and append decoded part
current = stringStack.pop().append(temp);
}
// opening bracket then push
else if(c == '['){
stringStack.push(current);
numStack.push(Integer.parseInt(number.toString()));
// clear
current = new StringBuilder();
number = new StringBuilder();
// if digit add to number
}else if(Character.isDigit(c)){
number.append(c);
// character
}else {
current.append(c);
}
}
// requires string
return current.toString();
}
}
// Your code here along with comments explaining your approach
// Approach 2: Using DFS
// Time Complexity : O(n * max(k))
// n: length of the String
// k: Multiplication factor
// Space Complexity : O(n)
// n: length of the String
// Stack space
class Problem2S2 {
// global index
int index = 0;
/** decode the string */
public String decodeString(String s) {
// edge case
if(s==null || s.length() ==0)
return s;
else
return depthFirst(s);
}
/** DFS */
private String depthFirst(String s){
// current string
StringBuilder current = new StringBuilder();
// number
int number = 0;
// traverse entire string
while(index<s.length()){
char c = s.charAt(index);
// pop operation means return -> BASE CASE
if(c == ']'){
return current.toString();
}// push means recursive call
else if(c == '['){
// next point
index++;
// get inner string
String innerString = depthFirst(s);
// decode it
StringBuilder temp = new StringBuilder();
while(number != 0){
temp.append(innerString);
number--;
}
// add to current
current.append(temp);
// type number
}else if(Character.isDigit(c)){
number = number*10 + c - '0';
}else {
current.append(c);
}
// increase index
index++;
}
// return as String
return current.toString();
}
}