10000 refactor 269 · hiradha/Leetcode@8a37509 · GitHub
[go: up one dir, main page]
Skip to content

Commit 8a37509

Browse files
fishercoder1534fishercoder1534
committed
refactor 269
1 parent 2a0fcc4 commit 8a37509

File tree

2 files changed

+76
-55
lines changed

2 files changed

+76
-55
lines changed

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

Lines changed: 52 additions & 55 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,5 @@
11
package com.fishercoder.solutions;
22

3-
43
import java.util.HashMap;
54
import java.util.HashSet;
65
import java.util.LinkedList;
@@ -34,70 +33,68 @@
3433
There may be multiple valid order of letters, return any one of them is fine.
3534
*/
3635
public class _269 {
36+
public static class Solution1 {
3737

38-
/**reference: https://discuss.leetcode.com/topic/28308/java-ac-solution-using-bfs*/
39-
public static String alienOrder(String[] words) {
40-
Map<Character, Set<Character>> map = new HashMap();
41-
Map<Character, Integer> degree = new HashMap<>();
42-
String result = "";
43-
if (words == null || words.length == 0) {
44-
return result;
45-
}
46-
for (String s : words) {
47-
for (char c : s.toCharArray()) {
48-
degree.put(c, 0);//keeps overwriting it, the purpose is to create one entry
49-
//for each letter in the degree map
38+
/**
39+
* reference: https://discuss.leetcode.com/topic/28308/java-ac-solution-using-bfs
40+
*/
41+
public String alienOrder(String[] words) {
42+
Map<Character, Set<Character>> map = new HashMap();
43+
Map<Character, Integer> degree = new HashMap<>();
44+
String result = "";
45+
if (words == null || words.length == 0) {
46+
return result;
5047
}
51-
}
52-
for (int i = 0; i < words.length - 1; i++) {
53-
String cur = words[i];
54-
String next = words[i + 1];
55-
int length = Math.min(cur.length(), next.length());
56-
for (int j = 0; j < length; j++) {
57-
char c1 = cur.charAt(j);
58-
char c2 = next.charAt(j);
59-
if (c1 != c2) {
60-
Set<Character> set = new HashSet<>();
61-
if (map.containsKey(c1)) {
62-
set = map.get(c1);
63-
}
64-
if (!set.contains(c2)) {
65-
set.add(c2);
66-
map.put(c1, set);
67-
degree.put(c2, degree.get(c2) + 1);
48+
for (String s : words) {
49+
for (char c : s.toCharArray()) {
50+
degree.put(c, 0);//keeps overwriting it, the purpose is to create one entry
51+
//for each letter in the degree map
52+
}
53+
}
54+
for (int i = 0; i < words.length - 1; i++) {
55+
String cur = words[i];
56+
String next = words[i + 1];
57+
int length = Math.min(cur.length(), next.length());
58+
for (int j = 0; j < length; j++) {
59+
char c1 = cur.charAt(j);
60+
char c2 = next.charAt(j);
61+
if (c1 != c2) {
62+
Set<Character> set = new HashSet<>();
63+
if (map.containsKey(c1)) {
64+
set = map.get(c1);
65+
}
66+
if (!set.contains(c2)) {
67+
set.add(c2);
68+
map.put(c1, set);
69+
degree.put(c2, degree.get(c2) + 1);
70+
}
71+
break;
6872
}
69-
break;
7073
}
7174
}
72-
}
73-
Queue<Character> queue = new LinkedList<>();
74-
for (char c : degree.keySet()) {
75-
if (degree.get(c) == 0) {
76-
queue.add(c);
75+
Queue<Character> queue = new LinkedList<>();
76+
for (char c : degree.keySet()) {
77+
if (degree.get(c) == 0) {
78+
queue.add(c);
79+
}
7780
}
78-
}
79-
while (!queue.isEmpty()) {
80-
char c = queue.remove();
81-
result += c;
82-
if (map.containsKey(c)) {
83-
for (char c2 : map.get(c)) {
84-
degree.put(c2, degree.get(c2) - 1);
85-
if (degree.get(c2) == 0) {
86-
queue.add(c2);
81+
while (!queue.isEmpty()) {
82+
char c = queue.remove();
83+
result += c;
84+
if (map.containsKey(c)) {
85+
for (char c2 : map.get(c)) {
86+
degree.put(c2, degree.get(c2) - 1);
87+
if (degree.get(c2) == 0) {
88+
queue.add(c2);
89+
}
8790
}
8891
}
8992
}
93+
if (result.length() != degree.size()) {
94+
return "";
95+
}
96+
return result;
9097
}
91-
if (result.length() != degree.size()) {
92-
return "";
93-
}
94-
return result;
9598
}
9699

97-
public static void main(String... args) {
98-
System.out.println("Hello world.");
99-
String[] words = new String[]{"wrt", "wrf", "er", "ett", "rftt"};
100-
String order = alienOrder(words);
101-
System.out.print(order);
102-
}
103100
}

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

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._269;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static org.junit.Assert.assertEquals;
8+
9+
public class _269Test {
10+
private static _269.Solution1 solution1;
11+
private static String[] words;
12+
13+
@BeforeClass
14+
public static void setup() {
15+
solution1 = new _269.Solution1();
16+
}
17+
18+
@Test
19+
public void test1() {
20+
words = new String[]{"wrt", "wrf", "er", "ett", "rftt"};
21+
assertEquals("wertf", solution1.alienOrder(words));
22+
}
23+
24+
}

0 commit comments

Comments
 (0)
0