|
Answer» Input: words[] = {"baa", "abcd", "abca", "cab", "cad"} Output: Order of characters is 'b', 'd', 'a', 'c' Because "baa" comes before "abcd" in the specified language, 'b' appears before 'a' in the result. Other orders can be found in the same way. The goal is to make a character graph and then figure out how to order it topologically. The detailed steps are listed below. - Make a graph g with the number of vertices equal to the size of the alien language's alphabet. For example, if the alphabet has a size of 5, words can have up to 5 characters. There have been no edges in the graph at first.
- Carry out the steps below for each pair of adjacent strings in the sorted array.
- Let word1 and word2 be the current pair of words. Compare the characters of both words one by one to locate the first mismatching character.
- Make an edge in g by mismatching a character in word1 with a character in word2.
- Print topological ordering of the graph you just made.
// C++#include<bits/stdc++.h>using namespace std; // CLASS for graph representationclass Graph{ int v; list<int> *adj; // A function that is used by topologicalSort void topologicalSortUtil(int v, bool visited[], STACK<int> &Stack);PUBLIC: Graph(int v); // Constructor // function to add an edge to the graph void addEdge(int v, int w); // displays a Topological SORT of the entire graph void topologicalSort();}; Graph::Graph(int v){ this->v = v; adj = new list<int>[v];} void Graph::addEdge(int v, int w){ adj[v].push_back(w); // Adding w to the list of v.} void Graph::topologicalSortUtil(int v, bool isVisited[], stack<int> &S){ // Mark the current node to be visited. isVisited[v] = true; // Repeat for all vertices that are adjacent to this vertex. list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) { if (visited[*i] == false) topologicalSortUtil(*i, isVisited, S); } // Push the current vertex to the stack which stores the result S.push(v);} void Graph::topologicalSort(){ stack<int> S; // Mark all the vertices as not visited bool *isVisited = new bool[v]; for (int i = 0; i < v; i++) isVisited[i] = false; // for (int i = 0; i < v; i++) if (isVisited[i] == false) topologicalSortUtil(i, isVisited, S); // Print contents of stack while (!S.empty()) { cout << (char) ('a' + S.top()) << " "; S.pop(); }} int min(int a, int b){ return (a < b)? a : b;} // This function finds and displays the order of characters from a sorted// array of words. N is the size of words[]. ‘a’ is set of all possible// alphabets.void print(string words[], int N, int a){ // Make a graph with 'a' edges Graph g(a); // Process all the adjacent pairs of words and make a graph for (int i = 0; i < N-1; i++) { // Take the two current words and wait for the first mismatching // character string s1 = words[i], s2 = words[i+1]; for (int k = 0; k < min(word1.length(), word2.length()); k++) { // If we encounter a mismatching character, we add an edge // from the character of s1 to that of s2 if (s1[k] != s2[k]) { g.addEdge(s1[k]-'a', s2[k]-'a'); break; } } } // Print the topological sort of the above graph g.topologicalSort();}// print function to be called in the main function
|
