# Topological Sort Solution in BFS and DFS by using HashMap<Character, List<Character>> to build graph.

• I think this problem is same as the Course Schedule
https://discuss.leetcode.com/topic/95602/5ms-dfs-beat-98-and-9ms-bfs-in-java
Besides, we need to output the topological sorted node.
and I use HashMap<Character,List<Character>> to build graph by comparing the 2 neighbor strings in dictionary to get the edge of graph.
eg. if "abc" and "abd" exit in dictionary, we could get an edge "c -> d".
And use HashSet to record the all letters shown in dictionary.

DFS:

``````public class Solution {
private String res;

public String alienOrder(String[] words) {
Map<Integer, List<Integer>> graph = makeGraph(words);

boolean[] visited = new boolean[26];
boolean[] finished = new boolean[26];
res = new String();

for(Integer s : graph.keySet()) {
if(!helper(graph, s, visited, finished)) {
return new String();
}
}

return res;
}

public Map<Integer, List<Integer>> makeGraph(String[] words) {
Map<Integer, List<Integer>> graph = new HashMap<>();
Set<Character> set = new HashSet<>();
//get all chars show in these dictionary
for(String word : words) {
for(char c : word.toCharArray()) {
}
}

for(Character c : set) {
graph.put(c - 'a', new ArrayList<Integer>());
}

for(int i = 0; i < words.length - 1; i++) {
int[] edge = getEdge(words[i], words[i + 1]);
if(edge != null) {
if(!graph.get(edge[0]).contains(edge[1])) {
}
}
}

return graph;
}

public int[] getEdge(String s1, String s2) {
int[] edge = new int[2];
int i = 0, j = 0;
while(i < s1.length() && j < s2.length()) {
if(s1.charAt(i) != s2.charAt(j)) break;
i++; j++;
}

if(i == s1.length() || j == s2.length()) {
edge = null;
} else {
edge[0] = s1.charAt(i) - 'a';
edge[1] = s2.charAt(j) - 'a';
}

return edge;
}

public boolean helper(Map<Integer, List<Integer>> graph, int s, boolean[] visited, boolean[] finished) {
if(finished[s]) {
return true;
} else if(visited[s]) {
return false;
} else {
visited[s] = true;
}

return false;
}
}

visited[s] = false;
finished[s] = true;
res = (char)(s + 'a') + res;
return true;
}

}
``````

BFS:

``````public class Solution {
public String alienOrder(String[] words) {
Set<Character> all = new HashSet<>();
for(String word : words) {
for(char c : word.toCharArray()) {
}
}

Map<Character,Integer> indegree = new HashMap<>();
Map<Character, List<Character>> graph = new HashMap<>();
int count = 0;
for(Character s : all) {
graph.put(s, new ArrayList<>());
indegree.put(s, 0);
}

for(int k = 0; k < words.length - 1; k++) {
int i = 0, j = 0;
String s1 = words[k], s2 = words[k + 1];
while(i < s1.length() && j < s2.length()) {
if(s1.charAt(i) != s2.charAt(j)) break;
i++; j++;
}
if(i == s1.length() || j == s2.length()) {
continue;
} else {
char c1 = s1.charAt(i), c2 = s2.charAt(j);
indegree.put(c2, indegree.get(c2) + 1);
count++;
}
}

for(Character s : all) {
if(indegree.get(s) == 0) {
q.offer(s);
}
}

StringBuffer res = new StringBuffer();
while(!q.isEmpty()) {
Character s = q.poll();
res.append(s);

count--;