# 3ms Clean Java Solution (DFS)

• The key to this problem is:

A topological ordering is possible if and only if the graph has no directed cycles

Let's build a graph and perform a DFS. The following states made things easier.

1. `visited[i] = -1`. Not even exist.
2. `visited[i] = 0`. Exist. Non-visited.
3. `visited[i] = 1`. Visiting.
4. `visited[i] = 2`. Visited.

Similarly, there is another simple BFS version.

``````private final int N = 26;
public String alienOrder(String[] words) {
int[] visited = new int[N];

StringBuilder sb = new StringBuilder();
for(int i = 0; i < N; i++) {
if(visited[i] == 0) {                 // unvisited
if(!dfs(adj, visited, sb, i)) return "";
}
}
return sb.reverse().toString();
}

public boolean dfs(boolean[][] adj, int[] visited, StringBuilder sb, int i) {
visited[i] = 1;                            // 1 = visiting
for(int j = 0; j < N; j++) {
if(visited[j] == 1) return false;  // 1 => 1, cycle
if(visited[j] == 0) {              // 0 = unvisited
if(!dfs(adj, visited, sb, j)) return false;
}
}
}
visited[i] = 2;                           // 2 = visited
sb.append((char) (i + 'a'));
return true;
}

public void buildGraph(String[] words, boolean[][] adj, int[] visited) {
Arrays.fill(visited, -1);                 // -1 = not even existed
for(int i = 0; i < words.length; i++) {
for(char c : words[i].toCharArray()) visited[c - 'a'] = 0;
if(i > 0) {
String w1 = words[i - 1], w2 = words[i];
int len = Math.min(w1.length(), w2.length());
for(int j = 0; j < len; j++) {
char c1 = w1.charAt(j), c2 = w2.charAt(j);
if(c1 != c2) {
adj[c1 - 'a'][c2 - 'a'] = true;
break;
}
}
}
}
}
``````

• mine is 5ms.

``````public class Solution {
public String alienOrder(String[] words) {
if (words == null || words.length < 1) return "";
int n = words.length, nAb = 26, k = 0;

char[][] chs = new char[nAb][];
for (int i = 0; i < n; i++) chs[i] = words[i].toCharArray();

List<Integer>[] map = new List[nAb];
buildEdge(chs[0], chs[0], map);
for (int i = 1; i < n; i++) buildEdge(chs[i - 1], chs[i], map);

boolean[] visited = new boolean[nAb], visiting = new boolean[nAb];
for (int i = 0; i < nAb; i++)
if (!visited[i] && map[i] != null) {
if (!dfs(i, visited, visiting, ans, map)) return "";
}
char[] output = new char[ans.size()];
for (Character c : ans) output[k++] = c;
return String.valueOf(output);
}

private void buildEdge(char[] a, char[] b, List<Integer>[] map) {
boolean done = false;
for (int i = 0, la = a.length, lb = b.length, len = Math.max(la, lb); i < len; i++) {
if (i < la && map[a[i] - 'a'] == null) map[a[i] - 'a'] = new ArrayList();
if (i < lb && map[b[i] - 'a'] == null) map[b[i] - 'a'] = new ArrayList();
if (!done && i < la && i < lb && a[i] != b[i]) {
done = true;
}
}
}

private boolean dfs(int c, boolean[] visited, boolean[] visiting, List<Character> ans, List<Integer>[] map) {
if (visiting[c]) return false;
visiting[c] = true;
for (int i : map[c])
if (!visited[i])
if (!dfs(i, visited, visiting, ans, map)) return false;
visiting[c] = false; visited[c] = true;
return true;
}
}``````

• I like this solution. Differentiating Visiting and Visited is a good idea.

• This post is deleted!

• @yavinci This solution won't work for a single word like ["wrtkj","wrt"]

• @shuoshankou

Why cannot this solution work on the given examples? When we only have a single word, the order can be arbitrary.

• This solution can work after inserting four lines of code in buildGraph(), after "String w1 = words[i - 1], w2 = words[i];"

``````    if (!w1.equals(w2) && w1.startsWith(w2)) {
Arrays.fill(visited, 2);
return;
}
``````

• The code returns wrong result with ["wrtkj","wrt"]: "wtrkj" instead of "".

• @avulanov This solution can work after inserting four lines of code in buildGraph(), after "String w1 = words[i - 1], w2 = words[i];"

``````    if (!w1.equals(w2) && w1.startsWith(w2)) {
Arrays.fill(visited, 2);
return;
}
``````

• @shiyanch Thanks, sorry I did not realize that you already posted it

• Well, this answer cannot pass this test case `["wrtkj","wrt"]`, either.

Who added this test case, it really helped a lot, man!

It stopped so many submits.

• @shiyanch Well, I don't think using `w1.startsWith(w2)` to avoid this specific test case is a good choice.

• sorry, I dont quite understand why do we need 4 status? is there any difference between visiting and visited?

• This post is deleted!

• can someone please explain the thinking behind building the graph? I mean what are we looking for when we try to build the graph from words? I completely don't get it.

• @zhugejunwei I agree. I think it will fail ["wrtkj","wrt", "wr"].

• @shelly1996 Yes there is a difference. Visiting means that node is "On recursion stack" presently. Visited means, it was already visited, not necessarily on recursion stack now.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.