Alien language problem in Java

Given the alphabetic sequence of an alien language, given a sorted dictionary (array of words) for the languages.

Example:

Words = { "aac", "abc", "aaa" }

Output

c, a, b

Algorithm:

(1) Compare two words that are next to each other at once, such as word1 with word2, word2 with word3,..., and word(startIndex) with the word(startIndex + 1).

(2) Next, we compare each character for the two words in question.

(2a) If the two characters are distinct, we stop comparing them at this point and determine that the character from word(startIndex) appears first.

(2b) If both elements are identical, we compare until one of the words is completed or until (2a) happens.

(3) This comparison process is repeated until all words have been evaluated.

Once a character set has been identified in (2a), we give it to the class "AlienCharacters," which is in charge of character ordering overall. The goal is to keep the elements in a sorted array in the proper sequence (DNode). A map (C# Dictionary) is utilized as an indexing object to reduce complexity to O and improve the insertion time into the linked list (1). This enhancement is compared to the prior approach, which employed topology sort.

Bounding circumstances:

1. The start index needs to be in the range.

2. If we exhaust one term when comparing two words, the size of the two words will vary. Only compare once an opponent has run out of fuel.

Filename:AlienLanguage.java

//Java Program for printing the order of characters in the alien language
import java. util.*;
// The class for graphs
class Graphs {


	// The array contains the list of all nodes in the adjective points
	private final LinkedList<Integer>[] adjacencyLists;
	Graphs(int nuVertices)
	{
		adjacencyLists = new LinkedList[nuVertices];
		for (int vertexIndexs = 0; vertexIndexs < nuVertices;
			vertexIndexs++) {
			adjacencyLists[vertexIndexs] = new LinkedList<>();
		}
	}
	// the method used for adding the edge of the graph to the vertex
	void addEdges(int startVertexs, int endVertexs)
	{
		adjacencyLists[startVertexs].add(endVertexs);
	}
	private int getNoOfVertices()
	{
		return adjacencyLists.length;
	}
	// the recursive call for sorting
	private void topologicalSortUtils(int currentVertexs, boolean[] visiteds, Stack<Integer> stacks)
	{
		// the current node is in the state of marked
		visiteds[currentVertexs] = true;
		// the function calls for all of the adjacent vertices in the graph
		for (int adjacentVertexs :
			adjacencyLists[currentVertexs]) {
			if (!visiteds[adjacentVertexs]) {
				topologicalSortUtils(adjacentVertexs, visiteds, stacks);
			}
		}
		// the current vertex is moved to the stack
		stacks.push(currentVertexs);
	}
	// the sort function of the vertices
	void topologicalSorts()
	{
		Stack<Integer> stacks = new Stack<>();
		// the remaining are then are marked
		boolean[] visiteds = new boolean[getNoOfVertices()];
		for (int i = 0; i < getNoOfVertices(); i++) {
			visiteds[i] = false;
		}
		// To save a Topological Sort beginning with all vertices
		//each one by one, call the recursion equipment and parts.
		for (int i = 0; i < getNoOfVertices(); i++) {
			if (!visiteds[i]) {
				topologicalSortUtils(i, visiteds, stacks);
			}
		}
		// display the elements of the stack
		while (!stacks.isEmpty()) {
			System.out.print((char)('a' + stacks.pop()) + " ");
		}
	}
}
public class AlienLanguage{
	// This function determines and displays the character 
	//order from a sorted array of words. 
	//The number of alphabet letters, starting with "a," 
	//is known as "alphas." For the sake of simplicity, 
	//just the first 'alpha' elements in the phrases array are allowed 
	//in this function. For instance, 
	//words should only contain letters 
	//'a', 'b', 'c', 'd', 'e', 'f', and 'g' if the alphas are 7.
	private static void printOrder(String[] words, int num, int alphas)
	{
		//the graph is created
		Graphs graphs = new Graphs(alphas);
		for (int i = 0; i < num - 1; i++) {
			// the initial 2 words are compared
			String words1 = words[i];
			String words2 = words[i + 1];
			for (int j = 0; j < Math.min(words1.length(), words2.length()); j++) {
				// if the character mismatches, it is added to the graph
				if (words1.charAt(j) != words2.charAt(j)) {
					graphs.addEdges(words1.charAt(j) - 'a',words2.charAt(j) - 'a');
					break;
				}
			}
		}
		// the sorted graph values are displayed
		graphs.topologicalSorts();
	}
	public static void main(String[] args)
	{
		String[] words = { "abc", "aac", "aba" };
		printOrder(words, 3, 3);
	}
}

Output

c a b

Analysis of Complexity:

For ease of comprehension, the following C# code includes method-wise time complexities.

If "N" is the total amount of words in the given alien language and "L" is the maximum word size, and "C" is the total amount of distinct characters.

Time Complexity: O(N*L)

Space Complexity: O(C)