269. Alien Dictionary

// LeetCode URL: https://leetcode.com/problems/alien-dictionary/
import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;

/**
 * Using DFS and topological sort
 *
 * Time Complexity: O(Vertices + Edges). Here number of edges is N-1, where N is
 * the no of words in the input array. Number of vertices equal to the unique
 * number of characters in input array. Thus Time Complexity: O(N * L + (N-1)) =
 * O(N * L). Where N is the average length of each character. In case the
 * character range is a..z then maximum number of unique characters will be 26.
 * In this can the time Complexity will become O(N).
 *
 * Space Complexity: O(Vertices + Edges). Refer to the above explaination of
 * time complexity.
 */
class Solution {
    public String alienOrder(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }
        if (words.length == 1) {
            return words[0];
        }

        HashMap<Character, HashSet<Character>> graph = buildGraph(words);
        HashSet<Character> visited = new HashSet<>();
        HashSet<Character> visiting = new HashSet<>();
        Stack<Character> order = new Stack<>();

        for (char c : graph.keySet()) {
            if (!visited.contains(c) && hasCycle(graph, c, visited, visiting, order)) {
                return "";
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!order.isEmpty()) {
            sb.append(order.pop());
        }

        return sb.toString();
    }

    private HashMap<Character, HashSet<Character>> buildGraph(String[] words) {
        HashMap<Character, HashSet<Character>> graph = new HashMap<>();

        for (String s : words) {
            for (char c : s.toCharArray()) {
                graph.put(c, new HashSet<>());
            }
        }

        for (int i = 1; i < words.length; i++) {
            char[] w1 = words[i - 1].toCharArray();
            char[] w2 = words[i].toCharArray();

            for (int j = 0; j < Math.min(w1.length, w2.length); j++) {
                if (w1[j] != w2[j]) {
                    graph.get(w1[j]).add(w2[j]);
                    break;
                }
            }
        }

        return graph;
    }

    private boolean hasCycle(HashMap<Character, HashSet<Character>> graph, char c, HashSet<Character> visited,
            HashSet<Character> visiting, Stack<Character> order) {

        // (visited.contains(c)) can be removed as it is redundant. Because we are
        // checking this before calling hasCycle function.
        if (visited.contains(c)) {
            return false;
        }
        if (visiting.contains(c)) {
            return true;
        }

        visiting.add(c);

        for (char n : graph.get(c)) {
            if (!visited.contains(n) && hasCycle(graph, n, visited, visiting, order)) {
                return true;
            }
        }

        visiting.remove(c);
        visited.add(c);
        order.push(c);
        return false;
    }
}