3ms Clean Java Solution (DFS)


  • 27

    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) {
        boolean[][] adj = new boolean[N][N];
        int[] visited = new int[N];
        buildGraph(words, adj, visited);
    
        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(adj[i][j]) {                        // connected
                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;
                    }
                }
            }
        }
    }
    

  • 0
    O

    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];
            List<Character> ans = new LinkedList();
            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;
                    map[a[i] - 'a'].add(b[i] - 'a');
                }
            }
        }
        
        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;
            ans.add(0, (char)(c + 'a'));
            return true;
        }
    }

  • 2
    S

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


  • 0
    This post is deleted!

  • 0
    S

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


  • 0
    M

    @shuoshankou

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


  • 1
    S

    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;
        }
    

  • 0
    A

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


  • 1
    S

    @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;
        }
    

  • 0
    A

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


  • 0

    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.


  • 1

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


  • 0
    S

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


  • 0
    G
    This post is deleted!

  • 0
    B

    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.


  • 0
    S

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


  • 0
    Z

    @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.


Log in to reply
 

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