In this blog post, we'll take on an interesting coding challenge. It's about figuring out the correct order of letters.
Challenge: The Alien Dictionary
Imagine you have been given a list of words representing an alien language sorted lexicographically from left to right. You need to determine the order of the characters in this alien language. Write a function alien_order(words) that takes a list of words as input and returns the character order of the alien language. If no such order exists, return an empty string. You can assume that the input consists of lowercase letters and that there will be no duplicate words.
Input: words: A list of strings representing words in the alien language. (2 <= len(words) <= 100, 1 <= len(words[i]) <= 20)
Output: A string representing the character order of the alien language.
Examples:
Input: words[] = {“baa”, “abcd”, “abca”, “cab”, “cad”}
Output: The order of characters is ‘b’, ‘d’, ‘a’, ‘c’
Explanation: Note that words are sorted and in the given language “baa” comes before “abcd”, therefore ‘b’ is before ‘a’ in output. Similarly, we can find other orders.
Input: words[] = {“caa”, “aaa”, “aab”}
Output: Order of characters is ‘c’, ‘a’, ‘b’
Alien Dictionary using Topological Sorting:
The approach to solving this challenge involves creating a directed graph, where each character represents a node, and edges between nodes indicate the relative order of characters. If the graph contains a cycle, a valid order of characters is not possible. Otherwise, we apply the topological sorting algorithm to determine the character order.
Following are the detailed steps:
The first step is to create a directed graph to represent the relative order of characters in the alien language.
Each character in the language corresponds to a node in the graph, and edges between nodes indicate the order of characters.
Step 2: Iterate Through Adjacent Words
Step 3: Add Edges to the Graph
Add directed edges in the graph based on the character order discovered in Step 2.
For each mismatched character in word1 and word2, add an edge from the character in word1 to the character in word2.
Step 4: Check for Cycles
To determine if a valid character order is possible, check if the graph contains any cycles.
Step 5: Perform Topological Sorting
If the graph is a Directed Acyclic Graph (DAG), perform topological sorting on the graph. Print the characters in topological order as the final output.
Solution in Java:
import java.util.*;
public class AlienDictionarySolver {
// Function to add a directed edge between characters u and v
private static void addEdge(List[] adj, int u, int v) {
adj[u].add(v);
}
// Depth-First Search (DFS) function to check for cycles in the graph
private static boolean dfs(List[] adj, int u, boolean[] visited, boolean[] recStack) {
visited[u] = true;
recStack[u] = true;
for (int v : adj[u]) {
if (!visited[v]) {
if (dfs(adj, v, visited, recStack)) {
return true;
}
} else if (recStack[v]) {
return true;
}
}
recStack[u] = false;
return false;
}
// Function to check if a cycle exists in the graph using DFS
private static boolean checkCycle(List[] adj, int V) {
boolean[] visited = new boolean[V];
boolean[] recStack = new boolean[V];
for (int i = 0; i < V; i++) {
if (!visited[i]) {
if (dfs(adj, i, visited, recStack)) {
return true;
}
}
}
return false;
}
// DFS-based topological sorting utility function
private static void topologicalSortUtil(List[] adj, int u, boolean[] visited, Stack stack) {
visited[u] = true;
for (int v : adj[u]) {
if (!visited[v]) {
topologicalSortUtil(adj, v, visited, stack);
}
}
stack.push(u);
}
// Function to perform topological sorting
private static void topologicalSort(List[] adj, int V) {
Stack stack = new Stack<>();
boolean[] visited = new boolean[V];
for (int i = 0; i < V; i++) {
if (!visited[i]) {
topologicalSortUtil(adj, i, visited, stack);
}
}
// Print the characters in topological order
while (!stack.isEmpty()) {
System.out.print((char) (stack.pop() + 'a') + " ");
}
}
// Function to process the words and find the character order
public static void findCharacterOrder(String[] words) {
int n = words.length;
// To track the frequency of characters
int[] freq = new int[26];
// Count unique characters and their frequencies
int k = 0;
for (String word : words) {
for (char c : word.toCharArray()) {
if (freq[c - 'a'] == 0) {
k++;
}
freq[c - 'a']++;
}
}
// Create adjacency list for the graph
List[] adj = new List[k];
for (int i = 0; i < k; i++) {
adj[i] = new ArrayList<>();
}
// Build the graph by iterating through adjacent words
for (int i = 0; i < n - 1; i++) {
String word1 = words[i];
String word2 = words[i + 1];
int j = 0;
while (j < word1.length() && j < word2.length()) {
if (word1.charAt(j) != word2.charAt(j)) {
// Add edges based on character order
addEdge(adj, word1.charAt(j) - 'a', word2.charAt(j) - 'a');
break;
}
j++;
}
}
// Check for cycles in the graph
if (checkCycle(adj, k)) {
System.out.println("Valid Order is not possible");
} else {
// Perform topological sorting and print character order
topologicalSort(adj, k);
}
}
public static void main(String[] args) {
String[] words1 = {"baa", "abcd", "abca", "cab", "cad"};
System.out.println("Example 1 Output:");
findCharacterOrder(words1);
String[] words2 = {"caa", "aaa", "aab"};
System.out.println("\nExample 2 Output:");
findCharacterOrder(words2);
}
}