So, we have to form the graph based on the chars in the list of words. Source will be char from word[i] and destination will be char from word [i+x] for eg. Then if there is cycle, we return "". If not, we return topological sort of string. Also, if the graph is not strongly connected, we can have multiple solutions.

Also, normal DFS will not work. For eg. Look at this graph:

graph LR;
	
	A --> B & C
	B --> C

We can get 2 answers - ABC, ACB. But ACB is wrong, as C is dependant on B. Hence, need to do something call post order DFS. Look at Topological Sorting.

Approach

Build the Graph:
- Create a directed graph using adjacency lists to depict character precedence.
- Add edges from the first differing character of adjacent words.
DFS with Cycle Detection:
- Use a visited map (or array) having three states:
  - 0: Not visited.
  - 1: Visited but still in the recursive stack (used to detect cycles).
  - 2: Fully processed.
- If a node is already being visited (state 1), a cycle exists.
Post-Order DFS for Topological Sort:
- Process all dependencies of a character before adding it to the result stack.
- Collect the characters in reverse topological order for proper sorting.

Code

[{"language":"Java","code":"class Solution {\n    public String alienOrder(String[] words) {\n        // Step 1: Build the Graph\n        Map<Character, List<Character>> graph = new HashMap<>();\n        Map<Character, Integer> visited = new HashMap<>(); // 0 = not visited, 1 = visiting, 2 = processed\n        for (String word : words) {\n            for (char ch : word.toCharArray()) {\n                if (!graph.containsKey(ch)) {\n                    graph.put(ch, new ArrayList<>());\n                    visited.put(ch, 0);\n                }\n            }\n        }\n\n        for (int i = 0; i < words.length - 1; i++) {\n            String w1 = words[i], w2 = words[i + 1];\n            if (w1.length() > w2.length() && w1.startsWith(w2)) {\n                return \"\"; // Invalid case: prefix issue\n            }\n            \n            for (int j = 0; j < Math.min(w1.length(), w2.length()); j++) {\n                char ch1 = w1.charAt(j), ch2 = w2.charAt(j);\n                if (ch1 != ch2) {\n                    graph.get(ch1).add(ch2);\n                    break;\n                }\n            }\n        }\n\n        // Step 2: DFS function\n        List<Character> ans = new ArrayList<>();\n        for (char ch : visited.keySet()) {\n            if (visited.get(ch) == 0 && !dfs(ch, graph, visited, ans)) {\n                return \"\";\n            }\n        }\n\n        // Step 3: Return result in reverse order\n        Collections.reverse(ans);\n        StringBuilder res = new StringBuilder();\n        for (char ch : ans) {\n            res.append(ch);\n        }\n        return res.toString();\n    }\n\n    private boolean dfs(char ch, Map<Character, List<Character>> graph, Map<Character, Integer> visited, List<Character> ans) {\n        if (visited.get(ch) == 1) { // Cycle detected\n            return false;\n        }\n        if (visited.get(ch) == 2) { // Already processed\n            return true;\n        }\n\n        visited.put(ch, 1); // Mark as visiting\n        for (char neighbour : graph.getOrDefault(ch, new ArrayList<>())) {\n            if (!dfs(neighbour, graph, visited, ans)) {\n                return false;\n            }\n        }\n\n        visited.put(ch

Related Tags