Dado un diccionario ordenado (array de palabras) de un idioma extranjero, encuentre el orden de los caracteres en el idioma.
Ejemplos:
Input: words[] = {"baa", "abcd", "abca", "cab", "cad"}
Output: Order of characters is 'b', 'd', 'a', 'c'
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'
Enfoque 1:
La idea es crear un gráfico de caracteres y luego encontrar la ordenación topológica del gráfico creado. Los siguientes son los pasos detallados.
1) Crea un gráfico g con un número de vértices igual al tamaño del alfabeto en el idioma extranjero dado. Por ejemplo, si el tamaño del alfabeto es 5, entonces puede haber 5 caracteres en las palabras. Inicialmente no hay bordes en el gráfico.
2) Haga lo siguiente para cada par de palabras adyacentes en una array ordenada dada.
…..a) Sea el par de palabras actual word1 y word2 . Uno por uno, compare los caracteres de ambas palabras y encuentre los primeros caracteres que no coinciden.
…..b) Crear una ventaja en g a partir del carácter no coincidente de la palabra 1a la de la palabra2 .
3) Imprima la clasificación topológica del gráfico creado anteriormente.
La implementación de lo anterior está en C++.
Complejidad del tiempo: el primer paso para crear un gráfico toma el tiempo O (n + alfa), donde n es el número de palabras dadas y alfa es el número de caracteres en el alfabeto dado. El segundo paso es también la clasificación topológica. Tenga en cuenta que habría vértices alfa y como máximo (n-1) bordes en el gráfico. La complejidad temporal de la clasificación topológica es O(V+E), que aquí es O(n + alfa). Entonces, la complejidad del tiempo general es O (n + alfa) + O (n + alfa), que es O (n + alfa).
Ejercicio: el código anterior no funciona cuando la entrada no es válida. Por ejemplo {“aba”, “bba”, “aaa”} no es válido, porque de las dos primeras palabras, podemos deducir que ‘a’ debe aparecer antes de ‘b’, pero de las dos últimas palabras, podemos deducir ‘b’ debe aparecer antes de ‘a’, lo cual no es posible. Extienda el programa anterior para manejar entradas no válidas y generar la salida como «No válida».
Enfoque 2: [Funciona para datos de entrada no válidos]
Hemos implementado este enfoque en C#.
Algoritmo:
(1) Compara 2 palabras adyacentes a la vez (es decir, palabra 1 con palabra 2, palabra 2 con palabra 3, …, palabra (índice de inicio) y palabra (índice de inicio + 1)
(2) Luego comparamos un carácter a la vez para las 2 palabras seleccionadas.
(2a) Si ambos caracteres son diferentes, detenemos la comparación aquí y concluimos que el carácter de word(startIndex) viene antes que el otro.
(2b) Si ambos caracteres son iguales, continuamos comparando hasta que ocurra (2a) o si alguna de las palabras se ha agotado.
(3) Continuamos comparando cada palabra de esta manera hasta que hayamos comparado todas las palabras.
Una vez que encontramos un conjunto de caracteres en (2a), los pasamos a la clase ‘AlienCharacters’, que se encarga del orden general de los caracteres. La idea es mantener el orden de los caracteres en una lista enlazada (DNode). Para optimizar el tiempo de inserción en la lista enlazada, se utiliza un mapa (Diccionario C#) como entidad de indexación, lo que reduce la complejidad a O(1). Esta es una mejora con respecto al algoritmo anterior en el que se utilizó la ordenación topológica para este fin.
Condiciones de borde:
1. El índice de inicio debe estar dentro del rango
2. Al comparar 2 palabras, si agotamos en una, es decir, la longitud de ambas palabras es diferente. Compare solo hasta que cualquiera de los dos se agote.
Análisis de Complejidad:
Las complejidades de tiempo en cuanto al método se han mencionado en el siguiente código (C#) para una mejor comprensión.
Si ‘N’ es el número de palabras en el diccionario/vocabulario extraterrestre de entrada, ‘L’ es la longitud de la palabra de longitud máxima y ‘C’ es el número final de caracteres únicos,
Complejidad de tiempo: O(N * L)
Complejidad espacial: O(C)
C++
// A C++ program to order of characters in an alien language
#include<bits/stdc++.h>
using namespace std;
// Class to represent a graph
class Graph
{
int V; // No. of vertices'
// Pointer to an array containing adjacency listsList
list<int> *adj;
// A function used by topologicalSort
void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
public:
Graph(int V); // Constructor
// function to add an edge to graph
void addEdge(int v, int w);
// prints a Topological Sort of the complete 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); // Add w to v’s list.
}
// A recursive function used by topologicalSort
void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)
{
// Mark the current node as visited.
visited[v] = true;
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
topologicalSortUtil(*i, visited, Stack);
// Push current vertex to stack which stores result
Stack.push(v);
}
// The function to do Topological Sort. It uses recursive topologicalSortUtil()
void Graph::topologicalSort()
{
stack<int> Stack;
// Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function to store Topological Sort
// starting from all vertices one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);
// Print contents of stack
while (Stack.empty() == false)
{
cout << (char) ('a' + Stack.top()) << " ";
Stack.pop();
}
}
int min(int x, int y)
{
return (x < y)? x : y;
}
// This function finds and prints order of character from a sorted
// array of words. n is size of words[]. alpha is set of possible
// alphabets.
// For simplicity, this function is written in a way that only
// first 'alpha' characters can be there in words array. For
// example if alpha is 7, then words[] should have only 'a', 'b',
// 'c' 'd', 'e', 'f', 'g'
void printOrder(string words[], int n, int alpha)
{
// Create a graph with 'alpha' edges
Graph g(alpha);
// Process all adjacent pairs of words and create a graph
for (int i = 0; i < n-1; i++)
{
// Take the current two words and find the first mismatching
// character
string word1 = words[i], word2 = words[i+1];
for (int j = 0; j < min(word1.length(), word2.length()); j++)
{
// If we find a mismatching character, then add an edge
// from character of word1 to that of word2
if (word1[j] != word2[j])
{
g.addEdge(word1[j]-'a', word2[j]-'a');
break;
}
}
}
// Print topological sort of the above created graph
g.topologicalSort();
}
// Driver program to test above functions
int main()
{
string words[] = {"caa", "aaa", "aab"};
printOrder(words, 3, 3);
return 0;
}
Java
// A Java program to order of
// characters in an alien language
import java.util.*;
// Class to represent a graph
class Graph {
// An array representing the graph as an adjacency list
private final LinkedList<Integer>[] adjacencyList;
Graph(int nVertices)
{
adjacencyList = new LinkedList[nVertices];
for (int vertexIndex = 0; vertexIndex < nVertices;
vertexIndex++) {
adjacencyList[vertexIndex] = new LinkedList<>();
}
}
// function to add an edge to graph
void addEdge(int startVertex, int endVertex)
{
adjacencyList[startVertex].add(endVertex);
}
private int getNoOfVertices()
{
return adjacencyList.length;
}
// A recursive function used by topologicalSort
private void topologicalSortUtil(int currentVertex,
boolean[] visited,
Stack<Integer> stack)
{
// Mark the current node as visited.
visited[currentVertex] = true;
// Recur for all the vertices adjacent to this
// vertex
for (int adjacentVertex :
adjacencyList[currentVertex]) {
if (!visited[adjacentVertex]) {
topologicalSortUtil(adjacentVertex, visited,
stack);
}
}
// Push current vertex to stack which stores result
stack.push(currentVertex);
}
// prints a Topological Sort of the complete graph
void topologicalSort()
{
Stack<Integer> stack = new Stack<>();
// Mark all the vertices as not visited
boolean[] visited = new boolean[getNoOfVertices()];
for (int i = 0; i < getNoOfVertices(); i++) {
visited[i] = false;
}
// Call the recursive helper function to store
// Topological Sort starting from all vertices one
// by one
for (int i = 0; i < getNoOfVertices(); i++) {
if (!visited[i]) {
topologicalSortUtil(i, visited, stack);
}
}
// Print contents of stack
while (!stack.isEmpty()) {
System.out.print((char)('a' + stack.pop())
+ " ");
}
}
}
public class OrderOfCharacters {
// This function finds and prints order
// of character from a sorted array of words.
// alpha is number of possible alphabets
// starting from 'a'. For simplicity, this
// function is written in a way that only
// first 'alpha' characters can be there
// in words array. For example if alpha
// is 7, then words[] should contain words
// having only 'a', 'b','c' 'd', 'e', 'f', 'g'
private static void printOrder(String[] words, int n,
int alpha)
{
// Create a graph with 'alpha' edges
Graph graph = new Graph(alpha);
for (int i = 0; i < n - 1; i++) {
// Take the current two words and find the first
// mismatching character
String word1 = words[i];
String word2 = words[i + 1];
for (int j = 0; j < Math.min(word1.length(),
word2.length());
j++) {
// If we find a mismatching character, then
// add an edge from character of word1 to
// that of word2
if (word1.charAt(j) != word2.charAt(j)) {
graph.addEdge(word1.charAt(j) - 'a',
word2.charAt(j) - 'a');
break;
}
}
}
// Print topological sort of the above created graph
graph.topologicalSort();
}
// Driver program to test above functions
public static void main(String[] args)
{
String[] words = { "caa", "aaa", "aab" };
printOrder(words, 3, 3);
}
}
// Contributed by Harikrishnan Rajan
C#
using System;
using System.Collections.Generic;
using System.Linq;
namespace AlienDictionary
{
public class DNode
{
public string Char;
public DNode prev = null;
public DNode next = null;
public DNode(string character) => Char = character;
}
public class AlienCharacters
{
public AlienCharacters(int k) => MaxChars = k;
private int MaxChars;
private DNode head = null;
private Dictionary<string, DNode> index = new Dictionary<string, DNode>();
// As we use Dictionary for indexing, the time complexity for inserting
// characters in order will take O(1)
// Time: O(1)
// Space: O(c), where 'c' is the unique character count.
public bool UpdateCharacterOrdering(string predChar, string succChar)
{
DNode pNode = null, sNode = null;
bool isSNodeNew = false, isPNodeNew = false;
if(!index.TryGetValue(predChar, out pNode))
{
pNode = new DNode(predChar);
index[predChar] = pNode;
isPNodeNew = true;
}
if (!index.TryGetValue(succChar, out sNode))
{
sNode = new DNode(succChar);
index[succChar] = sNode;
isSNodeNew = true;
}
// before ordering is formed, validate if both the nodes are already present
if (!isSNodeNew && !isPNodeNew)
{
if (!Validate(predChar, succChar))
return false;
}
else if ((isPNodeNew && !isSNodeNew) || (isPNodeNew && isSNodeNew))
InsertNodeBefore(ref pNode, ref sNode);
else
InsertNodeAfter(ref pNode, ref sNode);
if (pNode.prev == null)
head = pNode;
return true;
}
// Time: O(1)
private void InsertNodeAfter(ref DNode pNode, ref DNode sNode)
{
sNode.next = pNode?.next;
if (pNode.next != null)
pNode.next.prev = sNode;
pNode.next = sNode;
sNode.prev = pNode;
}
// Time: O(1)
private void InsertNodeBefore(ref DNode pNode, ref DNode sNode)
{
// insert pnode before snode
pNode.prev = sNode?.prev;
if (sNode.prev != null)
sNode.prev.next = pNode;
sNode.prev = pNode;
pNode.next = sNode;
}
// Time: O(1)
private bool Validate(string predChar, string succChar)
{
// this is the first level of validation
// validate if predChar node actually occurs before succCharNode.
DNode sNode = index[succChar];
while(sNode != null)
{
if (sNode.Char != predChar)
sNode = sNode.prev;
else
return true; // validation successful
}
// if we have reached the end and not found the predChar before succChar
// something is not right!
return false;
}
// Time: O(c), where 'c' is the unique character count.
public override string ToString()
{
string res = "";
int count = 0;
DNode currNode = head;
while(currNode != null)
{
res += currNode.Char + " ";
count++;
currNode = currNode.next;
}
// second level of validation
if (count != MaxChars) // something went wrong!
res = "ERROR!!! Input words not enough to find all k unique characters.";
return res;
}
}
class Program
{
static int k = 4;
static AlienCharacters alienCharacters = new AlienCharacters(k);
static List<string> vocabulary = new List<string>();
static void Main(string[] args)
{
vocabulary.Add("baa");
vocabulary.Add("abcd");
vocabulary.Add("abca");
vocabulary.Add("cab");
vocabulary.Add("cad");
ProcessVocabulary(0);
Console.WriteLine(alienCharacters.ToString());
Console.ReadLine();
}
// Time: O(vocabulary.Count + max(word.Length))
static void ProcessVocabulary(int startIndex)
{
if (startIndex >= vocabulary.Count - 1)
return;
var res = GetPredSuccChar(vocabulary.ElementAt(startIndex), vocabulary.ElementAt(startIndex + 1));
if (res != null)
{
if (!alienCharacters.UpdateCharacterOrdering(res.Item1, res.Item2))
{
Console.WriteLine("ERROR!!! Invalid input data, the words maybe in wrong order");
return;
}
}
ProcessVocabulary(startIndex + 1);
}
//Time: O(max(str1.Length, str2.Length)
static Tuple<string, string> GetPredSuccChar(string str1, string str2)
{
Tuple<string, string> result = null;
if (str1.Length == 0 || str2.Length == 0)
return null; // invalid condition.
if(str1[0] != str2[0]) // found an ordering
{
result = new Tuple<string, string>(str1[0].ToString(), str2[0].ToString());
return result;
}
string s1 = str1.Substring(1, str1.Length - 1);
string s2 = str2.Substring(1, str2.Length - 1);
if (s1.Length == 0 || s2.Length == 0)
return null; // recursion can stop now.
return GetPredSuccChar(s1, s2);
}
}
}
// Contributed by Priyanka Pardesi Ramachander
Javascript
<script>
// Javascript program to order of characters in an alien language
// Class to represent a graph
class Graph
{
constructor(V)
{
this.V = V;
this.adj = new Array(V);
for(let i = 0; i < V; i++)
this.adj[i] = [];
}
addEdge(v, w)
{
this.adj[v].push(w); // Add w to v’s list.
}
// A recursive function used by topologicalSort
topologicalSortUtil(v, visited, stack)
{
// Mark the current node as visited.
visited[v] = true;
// Recur for all the vertices adjacent to this vertex
this.adj[v].forEach(i => {
if(!visited[i])
this.topologicalSortUtil(i, visited, stack);
})
// Push current vertex to stack which stores result
stack.push(v);
}
// The function to do Topological Sort. It uses recursive topologicalSortUtil()
topologicalSort()
{
let stack = [];
// Mark all the vertices as not visited
let visited = new Array(this.V);
for (let i = 0; i < this.V; i++)
visited[i] = false;
// Call the recursive helper function to store Topological Sort
// starting from all vertices one by one
for (let i = 0; i < this.V; i++)
{
if (visited[i] == false)
this.topologicalSortUtil(i, visited, stack);
}
// Print contents of stack
while (stack.length > 0)
{
let x = stack.pop() + 'a'.charCodeAt(0);
document.write(String.fromCharCode(x) + " ");
}
}
}
// This function finds and prints order of character from a sorted
// array of words. n is size of words[]. alpha is set of possible
// alphabets.
// For simplicity, this function is written in a way that only
// first 'alpha' characters can be there in words array. For
// example if alpha is 7, then words[] should have only 'a', 'b',
// 'c' 'd', 'e', 'f', 'g'
function printOrder(words, n, alpha)
{
// Create a graph with 'alpha' edges
let g = new Graph(alpha);
// Process all adjacent pairs of words and create a graph
for (let i = 0; i < n-1; i++)
{
// Take the current two words and find the first mismatching
// character
word1 = words[i];
word2 = words[i+1];
for (let j = 0; j < Math.min(word1.length, word2.length); j++)
{
// If we find a mismatching character, then add an edge
// from character of word1 to that of word2
if (word1[j] != word2[j])
{
g.addEdge(word1.charCodeAt(j) - 'a'.charCodeAt(0), word2.charCodeAt(j) - 'a'.charCodeAt(0));
break;
}
}
}
// Print topological sort of the above created graph
g.topologicalSort();
}
// Driver program to test above functions
words = ["caa", "aaa", "aab"];
printOrder(words, 3, 3);
// This code is contributed by cavi4762
</script>
Producción:
c a b
Este artículo es una contribución de Piyush Gupta (C++), Harikrishnan Rajan (java) y Priyanka Pardesi Ramachander (C#) .
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA