Dada una array de palabras, encuentre cualquier orden alfabético en el alfabeto inglés de modo que las palabras dadas puedan considerarse ordenadas (crecientes), si existe tal orden, de lo contrario, la salida es imposible. Ejemplos:
Input : words[] = {"zy", "ab"}
Output : zabcdefghijklmnopqrstuvwxy
Basically we need to make sure that 'z' comes
before 'a'.
Input : words[] = {"geeks", "gamers", "coders",
"everyoneelse"}
Output : zyxwvutsrqponmlkjihgceafdb
Input : words[] = {"marvel", "superman", "spiderman",
"batman"
Output : zyxwvuptrqonmsbdlkjihgfeca
Enfoque ingenuo: el enfoque de fuerza bruta sería verificar todos los órdenes posibles y verificar si alguno de ellos satisface el orden de palabras dado. Teniendo en cuenta que hay 26 alfabetos en el idioma inglés, ¡hay 26! número de permutaciones que pueden ser órdenes válidas. Teniendo en cuenta que verificamos cada par para verificar un pedido, la complejidad de este enfoque va a O(26!*N^2) , que está mucho más allá de la complejidad de tiempo prácticamente preferida. Uso de clasificación topológica: esta solución requiere conocimiento de gráficos y su representación como listas de adyacencia , DFS y clasificación topológica. En nuestro orden requerido, se requiere imprimir letras de manera que cada letra debe ser seguida por las letras que se colocan en menor prioridad que ellas. Parece algo similar a cómo se define la clasificación topológica : en la clasificación topológica, necesitamos imprimir un vértice antes que sus vértices adyacentes. Definamos cada letra del alfabeto como Nodes en un gráfico dirigido estándar. Se dice que A está conectado con B (A—>B) si A precede a B en el orden. El algoritmo se puede formular de la siguiente manera:
- Si n es 1 , entonces cualquier pedido es válido.
- Tome las dos primeras palabras. Identifique la primera letra diferente (en el mismo índice de las palabras) en las palabras. La letra de la primera palabra precederá a la letra de la segunda palabra.
- Si no existe tal letra, entonces la primera string debe ser más pequeña que la segunda string.
- Asigne la segunda palabra a la primera palabra e ingrese la tercera palabra en la segunda palabra. Repita 2 , 3 y 4 (n-1) veces.
- Ejecute un recorrido DFS en orden topológico.
- Compruebe si se visitan todos los Nodes. En orden topológico, si hay ciclos en el gráfico, los Nodes de los ciclos quedan sin visitar, ya que no es posible visitar estos Nodes después de visitar todos los Nodes adyacentes. En tal caso, el orden no existe. En este caso, significa que el orden en nuestra lista se contradice.
CPP
/* CPP program to find an order of alphabets
so that given set of words are considered
sorted */
#include <bits/stdc++.h>
using namespace std;
#define MAX_CHAR 26
void findOrder(vector<string> v)
{
int n = v.size();
/* If n is 1, then any order works */
if (n == 1) {
cout << "abcdefghijklmnopqrstuvwxyz";
return;
}
/* Adjacency list of 26 characters*/
vector<int> adj[MAX_CHAR];
/* Array tracking the number of edges that are
inward to each node*/
vector<int> in(MAX_CHAR, 0);
// Traverse through all words in given array
string prev = v[0];
/* (n-1) loops because we already acquired the
first word in the list*/
for (int i = 1; i < n; ++i) {
string s = v[i];
/* Find first such letter in the present string that is different
from the letter in the previous string at the same index*/
int j;
for (j = 0; j < min(prev.length(), s.length()); ++j)
if (s[j] != prev[j])
break;
if (j < min(prev.length(), s.length())) {
/* The letter in the previous string precedes the one
in the present string, hence add the letter in the present
string as the child of the letter in the previous string*/
adj[prev[j] - 'a'].push_back(s[j] - 'a');
/* The number of inward pointing edges to the node representing
the letter in the present string increases by one*/
in[s[j] - 'a']++;
/* Assign present string to previous string for the next
iteration. */
prev = s;
continue;
}
/* If there exists no such letter then the string length of
the previous string must be less than or equal to the
present string, otherwise no such order exists*/
if (prev.length() > s.length()) {
cout << "Impossible";
return;
}
/* Assign present string to previous string for the next
iteration */
prev = s;
}
/* Topological ordering requires the source nodes
that have no parent nodes*/
stack<int> stk;
for (int i = 0; i < MAX_CHAR; ++i)
if (in[i] == 0)
stk.push(i);
/* Vector storing required order (anyone that satisfies) */
vector<char> out;
/* Array to keep track of visited nodes */
bool vis[26];
memset(vis, false, sizeof(vis));
/* Standard DFS */
while (!stk.empty()) {
/* Acquire present character */
char x = stk.top();
stk.pop();
/* Mark as visited */
vis[x] = true;
/* Insert character to output vector */
out.push_back(x + 'a');
for (int i = 0; i < adj[x].size(); ++i) {
if (vis[adj[x][i]])
continue;
/* Since we have already included the present
character in the order, the number edges inward
to this child node can be reduced*/
in[adj[x][i]]--;
/* If the number of inward edges have been removed,
we can include this node as a source node*/
if (in[adj[x][i]] == 0)
stk.push(adj[x][i]);
}
}
/* Check if all nodes(alphabets) have been visited.
Order impossible if any one is unvisited*/
for (int i = 0; i < MAX_CHAR; ++i)
if (!vis[i]) {
cout << "Impossible";
return;
}
for (int i = 0; i < out.size(); ++i)
cout << out[i];
}
// Driver code
int main()
{
vector<string> v{ "efgh", "abcd" };
findOrder(v);
return 0;
}
Java
/* Java program to find an order of alphabets
so that given set of words are considered
sorted */
import java.util.ArrayList;
import java.util.Stack;
public class Sorted {
@SuppressWarnings("unchecked")
static void findOrder(String[] v)
{
int n = v.length;
int MAX_CHAR = 26;
/* If n is 1, then any order works */
if (n == 1) {
System.out.println(
"abcdefghijklmnopqrstuvwxyz");
return;
}
/* Adjacency list of 26 characters*/
ArrayList<Integer>[] adj = new ArrayList[MAX_CHAR];
for (int i = 0; i < MAX_CHAR; i++)
adj[i] = new ArrayList<Integer>();
/* Array tracking the number of edges that are
inward to each node*/
int[] in = new int[MAX_CHAR];
// Traverse through all words in given array
String prev = v[0];
/* (n-1) loops because we already acquired the
first word in the list*/
for (int i = 1; i < n; ++i) {
String s = v[i];
/* Find first such letter in the present string
that is different from the letter in the
previous string at the same index*/
int j;
for (j = 0;
j < Math.min(prev.length(), s.length());
++j)
if (s.charAt(j) != prev.charAt(j))
break;
if (j < Math.min(prev.length(), s.length())) {
/* The letter in the previous string
precedes the one in the present string,
hence add the letter in the present string
as the child of the letter in the previous
string*/
adj[prev.charAt(j) - 'a'].add(s.charAt(j)
- 'a');
/* The number of inward pointing edges to
the node representing the letter in the
present string increases by one*/
in[s.charAt(j) - 'a']++;
/* Assign present string to previous string
for the next iteration. */
prev = s;
continue;
}
/* If there exists no such letter then the
string length of the previous string must be
less than or equal to the present string,
otherwise no such order exists*/
if (prev.length() > s.length()) {
System.out.println("Impossible");
return;
}
/* Assign present string to previous string for
the next iteration */
prev = s;
}
/* Topological ordering requires the source nodes
that have no parent nodes*/
Stack<Integer> stk = new Stack<Integer>();
for (int i = 0; i < MAX_CHAR; ++i)
if (in[i] == 0)
stk.push(i);
/* Vector storing required order (anyone that
* satisfies) */
ArrayList<Character> out
= new ArrayList<Character>();
/* Array to keep track of visited nodes */
boolean[] vis = new boolean[26];
/* Standard DFS */
while (!stk.empty()) {
/* Acquire present character */
int x = stk.peek();
stk.pop();
/* Mark as visited */
vis[x] = true;
/* Insert character to output vector */
out.add((char)((char)x + 'a'));
for (int i = 0; i < adj[x].size(); ++i) {
if (vis[adj[x].get(i)])
continue;
/* Since we have already included the
present character in the order, the number
edges inward to this child node can be
reduced*/
in[adj[x].get(i)]--;
/* If the number of inward edges have been
removed, we can include this node as a
source node*/
if (in[adj[x].get(i)] == 0)
stk.push(adj[x].get(i));
}
}
/* Check if all nodes(alphabets) have been visited.
Order impossible if any one is unvisited*/
for (int i = 0; i < MAX_CHAR; ++i)
if (!vis[i]) {
System.out.println("Impossible");
return;
}
for (int i = 0; i < out.size(); ++i)
System.out.print(out.get(i));
}
// Driver code
public static void main(String[] args)
{
String[] v = { "efgh", "abcd" };
findOrder(v);
}
}
// This code is contributed by Lovely Jain
Python3
# Python program to find an order of alphabets
# so that given set of words are considered
# sorted
MAX_CHAR = 26
def findOrder(v):
n = len(v)
# If n is 1, then any order works
if (n == 1):
print("abcdefghijklmnopqrstuvwxyz")
return
# Adjacency list of 26 characters
adj = [[] for i in range(MAX_CHAR)]
# Array tracking the number of edges that are
# inward to each node
In = [0 for i in range(MAX_CHAR)]
# Traverse through all words in given array
prev = v[0]
# (n-1) loops because we already acquired the
# first word in the list
for i in range(1,n):
s = v[i]
# Find first such letter in the present string that is different
# from the letter in the previous string at the same index
for j in range(min(len(prev), len(s))):
if (s[j] != prev[j]):
break
if (j < min(len(prev), len(s))):
# The letter in the previous string precedes the one
# in the present string, hence add the letter in the present
# string as the child of the letter in the previous string
adj[ord(prev[j]) - ord('a')].append(ord(s[j]) - ord('a'))
# The number of inward pointing edges to the node representing
# the letter in the present string increases by one
In[ord(s[j]) - ord('a')] += 1
# Assign present string to previous string for the next
# iteration.
prev = s
continue
# If there exists no such letter then the string length of
# the previous string must be less than or equal to the
# present string, otherwise no such order exists*
if (len(prev) > len(s)):
print("Impossible")
return
# Assign present string to previous string for the next
# iteration
prev = s
# Topological ordering requires the source nodes
# that have no parent nodes
stk = []
for i in range(MAX_CHAR):
if (In[i] == 0):
stk.append(i)
# Vector storing required order (anyone that satisfies) */
out = []
# Array to keep track of visited nodes */
vis = [False for i in range(26)]
# Standard DFS */
while (len(stk) > 0):
# Acquire present character */
x = stk.pop()
# Mark as visited */
vis[x] = True
# Insert character to output vector */
out.append(chr(x + ord('a')))
for i in range(len(adj[x])):
if (vis[adj[x][i]]):
continue
# Since we have already included the present
# character in the order, the number edges inward
# to this child node can be reduced
In[adj[x][i]] -= 1
# If the number of inward edges have been removed,
# we can include this node as a source node
if (In[adj[x][i]] == 0):
stk.append(adj[x][i])
# Check if all nodes(alphabets) have been visited.
# Order impossible if any one is unvisited
for i in range(MAX_CHAR):
if (vis[i] == 0):
print("Impossible")
return
for i in range(len(out)):
print(out[i],end="")
# Driver code
v = [ "efgh", "abcd" ]
findOrder(v)
# This code is contributed by shinjanpatra
Javascript
<script>
/* JavaScript program to find an order of alphabets
so that given set of words are considered
sorted */
const MAX_CHAR = 26
function findOrder(v)
{
let n = v.length;
/* If n is 1, then any order works */
if (n == 1) {
document.write("abcdefghijklmnopqrstuvwxyz");
return;
}
/* Adjacency list of 26 characters*/
let adj = new Array(MAX_CHAR).fill(0).map(()=>[]);
/* Array tracking the number of edges that are
inward to each node*/
let In = new Array(MAX_CHAR).fill(0);
// Traverse through all words in given array
let prev = v[0];
/* (n-1) loops because we already acquired the
first word in the list*/
for (let i = 1; i < n; ++i) {
let s = v[i];
/* Find first such letter in the present string that is different
from the letter in the previous string at the same index*/
let j;
for (j = 0; j < Math.min(prev.length, s.length); ++j)
if (s[j] != prev[j])
break;
if (j < Math.min(prev.length, s.length)) {
/* The letter in the previous string precedes the one
in the present string, hence add the letter in the present
string as the child of the letter in the previous string*/
adj[prev.charCodeAt(j) - 'a'.charCodeAt(0)].push(s.charCodeAt(j) - 'a'.charCodeAt(0));
/* The number of inward pointing edges to the node representing
the letter in the present string increases by one*/
In[s.charCodeAt(j) - 'a'.charCodeAt(0)]++;
/* Assign present string to previous string for the next
iteration. */
prev = s;
continue;
}
/* If there exists no such letter then the string length of
the previous string must be less than or equal to the
present string, otherwise no such order exists*/
if (prev.length > s.length) {
document.write("Impossible");
return;
}
/* Assign present string to previous string for the next
iteration */
prev = s;
}
/* Topological ordering requires the source nodes
that have no parent nodes*/
let stk = [];
for (let i = 0; i < MAX_CHAR; ++i)
if (In[i] == 0)
stk.push(i);
/* Vector storing required order (anyone that satisfies) */
let out = [];
/* Array to keep track of visited nodes */
let vis = new Array(26).fill(false);
/* Standard DFS */
while (stk.length > 0) {
/* Acquire present character */
let x = stk.pop();
/* Mark as visited */
vis[x] = true;
/* Insert character to output vector */
out.push(String.fromCharCode(x + 'a'.charCodeAt(0)));
for (let i = 0; i < adj[x].length; ++i) {
if (vis[adj[x][i]])
continue;
/* Since we have already included the present
character in the order, the number edges inward
to this child node can be reduced*/
In[adj[x][i]]--;
/* If the number of inward edges have been removed,
we can include this node as a source node*/
if (In[adj[x][i]] == 0)
stk.push(adj[x][i]);
}
}
/* Check if all nodes(alphabets) have been visited.
Order impossible if any one is unvisited*/
for (let i = 0; i < MAX_CHAR; ++i)
if (!vis[i]) {
document.write("Impossible");
return;
}
for (let i = 0; i < out.length; ++i)
document.write(out[i]);
}
// Driver code
let v = [ "efgh", "abcd" ];
findOrder(v);
// This code is contributed by shinjanpatra
</script>
Producción :
zyxwvutsrqponmlkjihgfeadcb
La complejidad de este enfoque es O(N*|S|) + O(V+E) , donde |V| =26 (el número de Nodes es el mismo que el número de alfabetos) y |E| < N (ya que como máximo se crea 1 borde para cada palabra como entrada). Por lo tanto, la complejidad general es O(N*|S|+N) . |S| representa la longitud de cada palabra.
Publicación traducida automáticamente
Artículo escrito por memezAreDreamz y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA