Skip to content

Commit d9a0b06

Browse files
fishercoder1534fishercoder1534
committed
refactor 316
1 parent f397c6d commit d9a0b06

File tree

2 files changed

+67
-60
lines changed

2 files changed

+67
-60
lines changed

‎src/main/java/com/fishercoder/solutions/_316.java

Lines changed: 50 additions & 44 deletions
Original file line numberDiff line numberDiff line change
@@ -18,58 +18,64 @@
1818
Return "acdb"
1919
*/
2020
public class _316 {
21-
/**credit: https://discuss.leetcode.com/topic/32259/java-solution-using-stack-with-comments/2*/
22-
public String removeDuplicateLetters_use_stack(String s) {
23-
int[] res = new int[26]; //will contain number of occurences of character (i+'a')
24-
boolean[] visited = new boolean[26]; //will contain if character (i+'a') is present in current result Stack
25-
char[] ch = s.toCharArray();
26-
for (char c : ch) { //count number of occurences of character
27-
res[c - 'a']++;
28-
}
29-
Deque<Character> st = new ArrayDeque<>(); // answer stack
30-
int index;
31-
for (char c : ch) {
32-
index = c - 'a';
33-
res[index]--; //decrement number of characters remaining in the string to be analysed
34-
if (visited[index]) {
35-
//if character is already present in stack, dont bother
36-
continue;
21+
public static class Solution1 {
22+
/** credit: https://discuss.leetcode.com/topic/32259/java-solution-using-stack-with-comments/2 */
23+
public String removeDuplicateLetters(String s) {
24+
int[] res = new int[26]; //will contain number of occurences of character (i+'a')
25+
boolean[] visited =
26+
new boolean[26]; //will contain if character (i+'a') is present in current result Stack
27+
char[] ch = s.toCharArray();
28+
for (char c : ch) { //count number of occurences of character
29+
res[c - 'a']++;
3730
}
38-
//if current character is smaller than last character in stack which occurs later in the string again
39-
//it can be removed and added later e.g stack = bc remaining string abc then a can pop b and then c
40-
while (!st.isEmpty() && c < st.peek() && res[st.peek() - 'a'] != 0) {
41-
visited[st.pop() - 'a'] = false;
31+
Deque<Character> st = new ArrayDeque<>(); // answer stack
32+
int index;
33+
for (char c : ch) {
34+
index = c - 'a';
35+
res[index]--; //decrement number of characters remaining in the string to be analysed
36+
if (visited[index]) {
37+
//if character is already present in stack, dont bother
38+
continue;
39+
}
40+
//if current character is smaller than last character in stack which occurs later in the string again
41+
//it can be removed and added later e.g stack = bc remaining string abc then a can pop b and then c
42+
while (!st.isEmpty() && c < st.peek() && res[st.peek() - 'a'] != 0) {
43+
visited[st.pop() - 'a'] = false;
44+
}
45+
st.push(c); //add current character and mark it as visited
46+
visited[index] = true;
4247
}
43-
st.push(c); //add current character and mark it as visited
44-
visited[index] = true;
45-
}
4648

47-
StringBuilder sb = new StringBuilder();
48-
//pop character from stack and build answer string from back
49-
while (!st.isEmpty()) {
50-
sb.insert(0, st.pop());
49+
StringBuilder sb = new StringBuilder();
50+
//pop character from stack and build answer string from back
51+
while (!st.isEmpty()) {
52+
sb.insert(0, st.pop());
53+
}
54+
return sb.toString();
5155
}
52-
return sb.toString();
5356
}
5457

55-
/**
56-
* Credit: https://discuss.leetcode.com/topic/31404/a-short-o-n-recursive-greedy-solution
57-
*/
58-
public String removeDuplicateLetters(String s) {
59-
int[] count = new int[26];
60-
int pos = 0; // the position for the smallest s[i]
61-
for (int i = 0; i < s.length(); i++) {
62-
count[s.charAt(i) - 'a']++;
63-
}
64-
for (int i = 0; i < s.length(); i++) {
65-
if (s.charAt(i) < s.charAt(pos)) {
66-
pos = i;
58+
public static class Solution2 {
59+
/**
60+
* Credit: https://discuss.leetcode.com/topic/31404/a-short-o-n-recursive-greedy-solution
61+
*/
62+
public String removeDuplicateLetters(String s) {
63+
int[] count = new int[26];
64+
int pos = 0; // the position for the smallest s[i]
65+
for (int i = 0; i < s.length(); i++) {
66+
count[s.charAt(i) - 'a']++;
6767
}
68-
count[s.charAt(i) - 'a']--;
69-
if (count[s.charAt(i) - 'a'] == 0) {
70-
break;
68+
for (int i = 0; i < s.length(); i++) {
69+
if (s.charAt(i) < s.charAt(pos)) {
70+
pos = i;
71+
}
72+
count[s.charAt(i) - 'a']--;
73+
if (count[s.charAt(i) - 'a'] == 0) {
74+
break;
75+
}
7176
}
77+
return s.length() == 0 ? "" : s.charAt(pos) + removeDuplicateLetters(
78+
s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
7279
}
73-
return s.length() == 0 ? "" : s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
7480
}
7581
}

‎src/test/java/com/fishercoder/_316Test.java

Lines changed: 17 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -6,24 +6,25 @@
66

77
import static org.junit.Assert.assertEquals;
88

9-
/**
10-
* Created by stevesun on 6/2/17.
11-
*/
129
public class _316Test {
13-
private static _316 test;
10+
private static _316.Solution1 solution1;
11+
private static _316.Solution2 solution2;
1412

15-
@BeforeClass
16-
public static void setup() {
17-
test = new _316();
18-
}
13+
@BeforeClass
14+
public static void setup() {
15+
solution1 = new _316.Solution1();
16+
solution2 = new _316.Solution2();
17+
}
1918

20-
@Test
21-
public void test1() {
22-
assertEquals("abc", test.removeDuplicateLetters("bcabc"));
23-
}
19+
@Test
20+
public void test1() {
21+
assertEquals("abc", solution1.removeDuplicateLetters("bcabc"));
22+
assertEquals("abc", solution2.removeDuplicateLetters("bcabc"));
23+
}
2424

25-
@Test
26-
public void test2() {
27-
assertEquals("acdb", test.removeDuplicateLetters("cbacdcbc"));
28-
}
25+
@Test
26+
public void test2() {
27+
assertEquals("acdb", solution1.removeDuplicateLetters("cbacdcbc"));
28+
assertEquals("acdb", solution2.removeDuplicateLetters("cbacdcbc"));
29+
}
2930
}

0 commit comments

Comments
 (0)