Verificación de Orden en Diccionario Alienígena

Clase 4 de 35 • Curso de Algoritmos Avanzados: Patrones de Arrays y Strings

Resumen

¿Cuál es el problema planteado en Verifying Alien Dictionary?

En este fascinante ejercicio de programación, nos enfrentamos a un reto que aparece en entrevistas de empresas tecnológicas destacadas como Facebook, Microsoft y Google. El problema "Verifying Alien Dictionary" involucra una lengua alienígena que, inesperadamente, utiliza las letras que conocemos en el español, aunque posiblemente en un orden diferente. Se nos presenta un conjunto de palabras escritas en este idioma y debemos determinar si las palabras están ordenadas de acuerdo al orden alfabético definido para ese idioma.

¿Cómo entender lo que nos piden hacer?

Este problema se basa en una comparación lexicográfica de palabras:

Entradas:
- Una lista de palabras: por ejemplo, ["apple", "app"].
- Una string que define el orden del alfabeto en el idioma alienígena, como "hlabcdefgijkmnopqrstuvwxyz".
Salida:
- Un valor booleano: true si las palabras están ordenadas siguiendo las reglas del alfabeto alienígena; false en caso contrario.

¿Cómo interpretar las reglas para las palabras?

Para poder verificar si las palabras están ordenadas, debemos seguir estos pasos:

Construir un mapa que asigne un índice a cada letra en el alfabeto alienígena. Esto nos permitirá comparar rápidamente el orden relativo de dos letras.
Comparar las palabras de la lista una por una en el orden proporcionado, asegurándonos de que cada palabra sea menor o igual a la siguiente.
Basarnos en reglas similares a las de un diccionario tradicional: si una palabra es prefijo de otra, por ejemplo, "app" debería preceder a "apple".

¿Por qué las entrevistas de trabajo valoran este problema?

Este tipo de ejercicio mide varias habilidades esenciales en programación:

Comprensión de órdenes y estructuras de datos.
Capacidad de implementar lógicas de comparación personalizadas.
Organizar eficientemente el código para manipular cadenas y listas.

Aunque no es un problema extremadamente complejo, los entrevistadores buscan ver cómo los candidatos piensan sistemáticamente y cómo abordan desafíos que pueden requerir una comprensión detallada de algoritmos básicos y estructuras de datos.

¡Consejos para resolverlo!

Divide y vencerás: Rompe el problema en pasos más pequeños y abórdalos uno por uno.
Comentarios claros en el código: Ayuda a seguir el flujo de la lógica y es una buena práctica de programación.
Prueba, prueba y prueba: Usa diferentes casos de prueba para asegurar que tu solución cubra todos los escenarios.

Tómate el tiempo necesario para formular tu solución antes de avanzar. Este es un gran ejercicio para mejorar tus habilidades de programación y lógica, así que ¡anímate y pon a prueba tus conocimientos!

Leonel Veliz

student•

Para ayudar a otros que no entendieron a la primera y tuvieron que buscar en documentación en otros idiomas.

Primero: "lexicograficamente" para efectos de este problema es ordenar palabras de la misma manera en como un diccionario ordena las palabras.

conocer vs cono = cono deberia estar primero porque al ser mas corta, gana prioridad.

Entonces en el caso donde

palabras = [conocer, cono] orden_alfabeto= NUESTRO ALFABETO

da un RETURN false por lo que mencione mas arriba

David Alejandro Ramírez Pérez

student•

muchisimas gracias por la explicación!!! =O

Sergio Cassia

student•

Gracias Leonel. Dato fundamental el que aportas.

El término "lexicográfico" es raro, aplicado a esto. Aqui en Argentina, "Orden alfabético" parece el concepto correcto.

Existiendo un alfabeto, a la acción de ordenar palabras en función de ese alfabeto se le llama "ordenar alfabeticamente".

Usar la acepción de léxico como "diccionario" para de allí asumir que se trata de orden porque los diccionarios están ordenados alfabeticamente, supera ampliamente mi suspicacia.

Leonel Veliz

student•

Entonces la cosa seria algo como: recibimos dos entradas:

la primera es "palabras" un arreglo de strings
la segunda "orden_alfabeto" es un string

Debes decirme con un true/false si "palabras" esta ordenado como un diccionario si dicho diccionario tuviera un orden alfabetico como el ingresado en "orden_alfabetico"

Daniel Steven Arias Otalora

student•

Les comparto mi solucion en JavaScript

const alphabet0 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'q', 'x', 'y', 'z']
const alphabet1 = ['h', 'l', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'i', 'k', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'q', 'x', 'y', 'z']

function alienDictionary(wordsArray, dictionary) {
    dictionary = Array.from(dictionary)
    const comparer = (word1, word2) => {
        word1 = Array.from(word1)
        word2 = Array.from(word2)
        for (let index = 0; index < word1.length; index++) {
            const index1 = dictionary.findIndex(element => element === word1[index])
            const index2 = dictionary.findIndex(element => element === word2[index])
            if (index2 === index1) { }
            else if (index2 < index1) return false
            else return true
        }
    }
    for (let index = 0; index < wordsArray.length; index++) {
        if (index === 0) { }
        else if (!comparer(wordsArray[index - 1], wordsArray[index])) return false
    }
    return true
}

console.log(alienDictionary(['habito', 'hacer', 'lectura', 'sonreir'], alphabet1))

Nicolas Alpargatero

student•

Overview

En una lengua alienígena, sorprendentemente, también utilizan las letras del español, pero posiblemente en un orden diferente, una permutation de nuestro alfabeto
- Quiere decir que vamos a recibir el orden del alfabeto de otra forma
Dada una secuencia de palabras escritas en el idioma extranjero, y el orden del alfabeto, devuelve verdadero si y solo si las palabras dadas están ordenadas lexicográficamente en este idioma extranjero.
- Una lista de palabras conformadas por letras de un diccionario de caracteres que dan, y revisar si esta ordenado

Ejemplos

# Input
palabras = ['conocer', 'cono']
orden_alfabeto = 'abcdfghijklmnopqrstuvwxyz'
# Ouput: 
False

# Input
palabras = ['habito', 'hacer', 'lectura', 'sonreir']
orden_alfabeto - 'hlabcdefgikmnopqrstuvqxyz'
# Output:
True

David Elias Gatica Morales

student•

Lexicograficamente: de un modo relacionado con los diccionarios, o con la escritura, edición o compilación de diccionarios.

Ulises Antonio Sámano Galván

student•

//const palabras = ['habito', 'hacer', 'lectura', 'sonreir']

//const ordenDelAbecedario = ['h', 'l', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'i', 'k', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'q', 'x', 'y', 'z']

const palabras = ["conocer", "cono"]

const ordenDelAbecedario = [

'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',

'n', 'ñ', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'

];

let estanOrdenadas = true

for(let indiceDeLaPalabra = 0; indiceDeLaPalabra < palabras.length; indiceDeLaPalabra ++) {

if(palabras[indiceDeLaPalabra + 1] === undefined) {

break

}

const palabra = palabras[indiceDeLaPalabra]

const siguientePalabra = palabras[indiceDeLaPalabra + 1]

for(let indiceDeLaLetra = 0; indiceDeLaLetra < palabra.length; indiceDeLaLetra++) {

const letra = palabra[indiceDeLaLetra]

const letraDeLaSiguientePalabra = siguientePalabra[indiceDeLaLetra]

if(letra === letraDeLaSiguientePalabra) {

continue

}

let posicionDeLaLetraEnElAbecedario = 0

let posicionDeLaLetraDeLaSiguientePalabraEnElAbecedario = 0

for(let indiceDeLetraEnElAbecedario = 0; indiceDeLetraEnElAbecedario < ordenDelAbecedario.length; indiceDeLetraEnElAbecedario++){

if(ordenDelAbecedario[indiceDeLetraEnElAbecedario] === letra) {

posicionDeLaLetraEnElAbecedario = indiceDeLetraEnElAbecedario

break

}

for(let indiceDeLetraEnElAbecedario = 0; indiceDeLetraEnElAbecedario < ordenDelAbecedario.length; indiceDeLetraEnElAbecedario++){

if(ordenDelAbecedario[indiceDeLetraEnElAbecedario] === letraDeLaSiguientePalabra) {

posicionDeLaLetraDeLaSiguientePalabraEnElAbecedario = indiceDeLetraEnElAbecedario

break

}

if(posicionDeLaLetraEnElAbecedario > posicionDeLaLetraDeLaSiguientePalabraEnElAbecedario) {

estanOrdenadas = false

}

break

}

console.log(estanOrdenadas)

Sergio Cassia

student•

Mi resolución en Python:

def cargaDiccionario(alfabeto):
    # el diccionario se carga con el criterio de mayor valor para la primer letra del alfabeto y numeros descendentes secuenciales hasta el menor valor para la última letra
    # en el caso de abecedario accidental: a=26 y z=1
    dicc_tmp={}
    for i in range(0,len(alfabeto)):
        dicc_tmp[alfabeto[i].upper()]=len(alfabeto)-i
    return dicc_tmp

def palabras_ordenadas(palabra1,palabra2):
    # esta función devuelve True si palabra1 esta correctamente ordenada en relación a palabra2, de lo contrario devuelve false
    # -> No es case sensitive los textos se evaluan en mayúscula. Amor y aMOR son iguales.
    # -> cadena vacía o espacios vacíos se ordenan primero, por lo tanto [' ','hola','casa'] resuelve en Verdadero
    # -> Si en una cadena aparece un caracter que no está en el alfabeto,  se dá por concluida  la evaluación devolviendo False.
    palabra1=palabra1.upper()
    palabra2=palabra2.upper()

    # si ambas palabras son iguales, devuelve True
    if palabra1==palabra2:
        return True
    
    global dicc_alfabeto
    
    # tomo como referencia la primer palabra
    for i in range(0,len(palabra1)):
        # Si no se resolvió la comparación quiere decir que hubo igualdad. Luego, si el indice i que responde al len de palabra1 es mayor al len de palabra2
        # significa que hasta ahora son iguales pero  palabra1 es más larga que palabra2 y por ende, palabra2 debería estar primero. asi que devolvemos false
        if (i+1>len(palabra2)):
            return False
        # si aparece un caracter que no es una de las letras del alfabeto, devuelvo false
        if (palabra1[1] not in dicc_alfabeto or palabra2[1] not in dicc_alfabeto):
            return False
        # Si la letra evaluada en palabra1 es menor a la misma posición de letra en palabra2, devuelve False 
        if (dicc_alfabeto[palabra1[i]]<dicc_alfabeto[palabra2[i]]):
            return False
        # Si la letra evaluada en palabra1 es mayor a la misma posición de letra en palabra2, devuelve True
        if (dicc_alfabeto[palabra1[i]]>dicc_alfabeto[palabra2[i]]):
            return True
    
    # Para cualquier otra situación, se devuelve True
    return True

def valida_orden_lista(lista_palabras):
    for i in range(0,len(lista_palabras)-1):
        print ("indice {} es {}".format(i,lista_palabras[i]))
        if (palabras_ordenadas(lista_palabras[i].strip(),lista_palabras[i+1].strip())==False):
            return False
    return True


# Carga del alfabeto a utilizar  
#       alfabeto_alien='hlabcdefgijkmnopqrstuvqxyz'   
#       alfabeto_occid='abcdefghijklmnopqrstuvqxyz'
dicc_alfabeto=cargaDiccionario('hlabcdefgijkmnopqrstuvqxyz')

# listas de prueba
lista_palabras=['cono','conocer','foniatra']
lista_palabras=['hijo', 'hijos', 'papa', 'celular3']
lista_palabras=['hijos', ' ', 'papa']
valida_orden_lista(lista_palabras)

Daniel Ortiz

student•

Despues de mucho pensarlo logre algo en scala


import scala.util.control.Breaks.break

class alien\_words {
&#x20; private def generatePositions(arr: Array\[String]): Map\[Int, Int] = {
&#x20;   arr.zipWithIndex
&#x20;     .map {
&#x20;       case (item, index) => (index, 0)
&#x20;     }.toMap
&#x20; }

&#x20; private def generateMapValueAlphabet(str: String): Map\[Char, Int] ={
&#x20;   str
&#x20;     .toCharArray
&#x20;     .zipWithIndex
&#x20;     .map { case (char, index) =>
&#x20;       char -> index
&#x20;     }.toMap
&#x20; }

&#x20; private def sumItemsToMap(positionsVal: Map\[Int,Int],
&#x20;                           mapValue:Map\[Char,Int],
&#x20;                           arr: Array\[String],
&#x20;                           index:Int):
&#x20; Map\[Int, Int] = {
&#x20;   positionsVal.map {
&#x20;     case (key, value) => (key, value +
&#x20;       mapValue(arr(key)(index))
&#x20;     )
&#x20;   }
&#x20; }
&#x20; def processArray(arr: Array\[String], str: String): Boolean = {
&#x20;   var positionsVal = generatePositions(arr)
&#x20;val mapValue =generateMapValueAlphabet(str)
&#x20;   // Example logic: print each element of the array with the string
&#x20;   var index=0
&#x20;   while (true) {
&#x20;     try {
&#x20;       positionsVal = sumItemsToMap(
&#x20;         positionsVal,
&#x20;         mapValue,
&#x20;         arr,
&#x20;         index
&#x20;       )
&#x20;       var aux = positionsVal(0)
&#x20;       *println*(aux)
&#x20;       for (i <-1 until positionsVal.keys.size-1) {
&#x20;         if (aux>=positionsVal(i)){
&#x20;           aux=positionsVal(i)
&#x20;         }else{
&#x20;           return false
&#x20;         }
&#x20;       }
&#x20;       index += 1
&#x20;       if (index>3){
&#x20;         return true
&#x20;       }
&#x20;     } catch {
&#x20;       case e: IndexOutOfBoundsException=> return true
&#x20;     }
&#x20;   }
&#x20;   false
&#x20; }
}

object AlienWords {
&#x20; def main(args: Array\[String]): Unit = {
&#x20;   val word = Array("habito", "hacer", "lectura", "sonreir")
&#x20;   val orden\_alfabeto = "hlabcdefgijkmnopqrstuvwxyz"
&#x20;   val al = new alien\_words()

&#x20;   // Measure execution time
&#x20;   val startTime = System.*nanoTime*() // Start time in nanoseconds
&#x20;   al.processArray(word, orden\_alfabeto)

&#x20;   val endTime = System.*nanoTime*()   // End time in nanoseconds
&#x20;   val duration = (endTime - startTime) / 1e6  // Convert nanoseconds to milliseconds
&#x20;   *println*(s"Execution time: $duration ms")
&#x20; }
}

Miguel Angel Reyes Moreno

student•

La verdad es que no sé si lo que hice es correcto, pero al menos para los 2 ejemplos de la clase, obtuve los resultados esperados, comparto mi código en TypeScript:

Rodrigo Arredondo Rosas

student•

def validate_words(first_word, second_word, alphabet):
	first_word_letters = len(first_word)
	second_word_letters = len(second_word)
	letters = first_word_letters if first_word_letters <= second_word_letters else second_word_letters
	last_letter = letters - 1

	for position in range(letters):
		first_letter = first_word[position]
		second_letter = second_word[position]
		
		if first_letter != second_letter:
			# Only compare if letters don't match
			first_letter_index = alphabet.index(first_letter)
			second_letter_index = alphabet.index(second_letter)

			if first_letter_index < second_letter_index:
				break
			elif first_letter_index > second_letter_index:
				return False
		elif position == last_letter and first_word_letters > second_word_letters:
			# The same characters were compared through iterations
			# First word larger than second word (example liked - like)
			return False

	return True

	
def alien_dictionary_verifying(words, alphabet):
	increment = 1
	total_words = len(words)-1

	for position in range(total_words):
		first_word = words[position]
		second_word = words[position+increment]

		# Can improve by three words searching (previous, current, next)
		validation = validate_words(first_word, second_word, alphabet)

		if not validation:
			return False

	return True


words = ['hora', 'balon', 'celular', 'cono', 'con', 'desayuno', 'jugar']

first_alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 
					'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 
					'q', 'r', 's', 't', 'u', 'v', 'q', 'x', 'y', 'z']

second_alphabet = ['h', 'l', 'a', 'b', 'c', 'd', 'e', 'f', 
					'g', 'i', 'j', 'k', 'm', 'n', 'o', 'p', 'q', 
					'r', 's', 't', 'u', 'v', 'q', 'x', 'y', 'z']

print(alien_dictionary_verifying(words, second_alphabet))
```def validate\_words(first\_word, second\_word, alphabet):

&#x9;first\_word\_letters = len(first\_word)

&#x9;second\_word\_letters = len(second\_word)

&#x9;letters = first\_word\_letters if first\_word\_letters <= second\_word\_letters else second\_word\_letters

&#x9;last\_letter = letters - 1



&#x9;for position in range(letters):

&#x9;	first\_letter = first\_word\[position]

&#x9;	second\_letter = second\_word\[position]

&#x9;&#x9;

&#x9;	if first\_letter != second\_letter:

&#x9;		\# Only compare if letters don't match

&#x9;		first\_letter\_index = alphabet.index(first\_letter)

&#x9;		second\_letter\_index = alphabet.index(second\_letter)



&#x9;		if first\_letter\_index < second\_letter\_index:

&#x9;			break

&#x9;		elif first\_letter\_index > second\_letter\_index:

&#x9;			return False

&#x9;	elif position == last\_letter and first\_word\_letters > second\_word\_letters:

&#x9;		\# This means that the same characters were compared trough iterations

&#x9;		\# if the first word is larger it should be after the second word (example liked - like)

&#x9;		return False



&#x9;return True



&#x9;

def alien\_dictionary\_verifying(words, alphabet):

&#x9;increment = 1

&#x9;total\_words = len(words)-1



&#x9;for position in range(total\_words):

&#x9;	first\_word = words\[position]

&#x9;	second\_word = words\[position+increment]



&#x9;	\# Can improve by three words searching (previous, current, next)

&#x9;	validation = validate\_words(first\_word, second\_word, alphabet)



&#x9;	if not validation:

&#x9;		return False



&#x9;return True





words = \['hora', 'balon', 'celular', 'cono', 'con', 'desayuno', 'jugar']



first\_alphabet = \['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l',&#x20;

&#x9;				'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'q', 'x', 'y', 'z']



second\_alphabet = \['h', 'l', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'i', 'j', 'k',&#x20;

&#x9;				'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'q', 'x', 'y', 'z']



print(alien\_dictionary\_verifying(words, second\_alphabet))

Xavier Flores

student•

Mi solución en Python de complejidad O(n) ya que el segundo for es pequeño:

word = ["habito", "hacer", "lectura", "sonreir"]
orden_alfabeto = "hlabcdefgijkmnopqrstuvwxyz"

def verifying_alien(array,orden_alfabeto):
    count_array= len(array)
    array_alphabeth= list(orden_alfabeto)

    for i in range (1,count_array):
        previusWord= list(word[i-1])    
        nextWord= list(word[i])    
        len_previusWord= len(previusWord)
        len_nextWord= len(nextWord)
        less_letter=0

        if (len_previusWord<len_nextWord):
            less_letter=len_previusWord
        else:
            less_letter=len_nextWord

        for y in range (less_letter):
            if (previusWord[y]==nextWord[y]):
                if (len_nextWord<len_previusWord and (y+1)==less_letter):
                    return False
            elif (array_alphabeth.index(previusWord[y])<array_alphabeth.index(nextWord[y])):
                break
            else:
                return False
    return True

print(verifying_alien(word,orden_alfabeto))

Basilio Gianfranco De Paula Cuevas

student•

Construi la siguiente solución luego de analizar el problema, me di cuenta que es posible optimizar el algoritmo analizando la valía de la letra mediante el indice en la cadena de diccionario por lo que no es necesario construir la 1era función que puntua las letras. Que creen si ustedes lo mejoran?

# Receive the alphabet and give points to a letter
def alphabet_value(alphabet):
    new_alphabet = {}
    num = 1

    for letter in alphabet:
        new_alphabet[letter] = num
        num += 1

    return new_alphabet

# Verify the if the words order is correct
def verify_sort(words, alphabet):

    for index in range(len(words)-1):
        for index_two in range(len(words[index])):
            try:
                current_word_point = order_alphabet[words[index][index_two]]
                next_word_point = order_alphabet[words[index+1][index_two]]

                if current_word_point == next_word_point:
                    continue
                elif current_word_point < next_word_point:
                    break
                else:
                    return False
            except IndexError:
                return False

    return True

order_alphabet = 'hlabcdefgijkmnopqrstuvwxyz'
list_words = ['habito', 'hacer', 'lectura', 'sonreir']

order_alphabet = alphabet_value(order_alphabet)

print(verify_sort(list_words, order_alphabet))

Xavier Flores

student•

pues creo que mi solución es bastante similar a la tuya:

word = ["habito", "hacer", "lectura", "sonreir"]
orden_alfabeto = "hlabcdefgijkmnopqrstuvwxyz"


def verifying_alien(array,orden_alfabeto):
    count_array= len(array)
    array_alphabeth= list(orden_alfabeto)

    for i in range (1,count_array):
        previusWord= list(word[i-1])    
        nextWord= list(word[i])    
        len_previusWord= len(previusWord)
        len_nextWord= len(nextWord)
        less_letter=0

        if (len_previusWord<len_nextWord):
            less_letter=len_previusWord
        else:
            less_letter=len_nextWord

        for y in range (less_letter):
            if (previusWord[y]==nextWord[y]):
                if (len_nextWord<len_previusWord and (y+1)==less_letter):
                    return False
            elif (array_alphabeth.index(previusWord[y])<array_alphabeth.index(nextWord[y])):
                break
            else:
                return False
    return True

print(verifying_alien(word,orden_alfabeto))

Armando Salamanca Ayon

student•

Como un aporte anterior pero con TypeScript

const  alienDictionary =(wordsArray:Array<string>, dictionary:string):boolean=> {
  const alienAlphabet = [...dictionary];
  const comparer = (word1:string, word2:string) => {
      for (let index = 0; index < [...word1].length; index++) {
            const index1 = alienAlphabet.findIndex((element:string) => element === word1[index])
            const index2 = alienAlphabet.findIndex((element:string) => element === word2[index])
            if (index2 === index1) { }
            else if (index2 < index1) return false
            else return true
        }
    }
    for (let index = 1; index < wordsArray.length; index++) {
       
        if (!comparer(wordsArray[index - 1], wordsArray[index])) return false
    }
    return true
}
```const  alienDictionary =(wordsArray:Array\<string>, dictionary:string):boolean=> {

&#x20; const alienAlphabet = \[...dictionary];

&#x20; const comparer = (word1:string, word2:string) => {

&#x20;     for (let index = 0; index < \[...word1].length; index++) {

&#x20;           const index1 = alienAlphabet.findIndex((element:string) => element === word1\[index])

&#x20;           const index2 = alienAlphabet.findIndex((element:string) => element === word2\[index])

&#x20;           if (index2 === index1) { }

&#x20;           else if (index2 < index1) return false

&#x20;           else return true

&#x20;       }

&#x20;   }

&#x20;   for (let index = 1; index < wordsArray.length; index++) {

&#x20;     &#x20;

&#x20;       if (!comparer(wordsArray\[index - 1], wordsArray\[index])) return false

&#x20;   }

&#x20;   return true

}

Yojan Antonio Pardo Zabala

student•

esta es mi solución en java, tomo en cuenta los casos para evaluar el tamaño de las palabras y prevenir un IndexOutOfBundException

```java public class AlienDictionary {

public static void main(String[] args) {
    String humanAlphabet = "abcdefghijklmnopqrstuvwxyz";
    String alienAlphabet = "yhesocvxduiglbkrztnwjpfmaq";

    String[] words = {"habito", "hacer", "lectura", "sonreir"};

    System.out.println("validating words with human alphabet");
    System.out.println(validateWordsWithAlphabet(words, humanAlphabet));
    System.out.println("validating words with alien alphabet");
    System.out.println(validateWordsWithAlphabet(words, alienAlphabet));
}

private static boolean validateWordsWithAlphabet(String[] words, String alphabet) {
    for(int i = 0; i < words.length - 1; i++) {
        String word1 = words[i];
        String word2 = words[i + 1];
        boolean isEquals = true;
        for(int j = 0; j < Math.min(word1.length(), word2.length()); j++) {
            char letter1 = word1.charAt(j);
            char letter2 = word2.charAt(j);
            int index1 = alphabet.indexOf(letter1);
            int index2 = alphabet.indexOf(letter2);
            if(index1 > index2) {
                return false;
            } else if(index1 < index2) {
                isEquals = false;
                break;
            }
        }

        if(isEquals && word1.length() > word2.length()) {
            return false;
        }
    }
    return true;
}

}

franklin yancoba

student•

   public bool DiccionaryAlien(List<string> ListWord, string DiccionaryAlphabet) {
            for (int i = 0; i < ListWord.Count(); i++) {
                char characterFirstWord = ListWord[i][0];
                int indexFoundCharacter = isCharacterInDiccionary(DiccionaryAlphabet, characterFirstWord);
                if (indexFoundCharacter==-1) {
                    return false;
                }
                int getNextIndexElementWord= i+1;
                if (ListWord.Count()== getNextIndexElementWord) {
                    break;
                }
                int nextIndexFoundCharacter = isCharacterInDiccionary(DiccionaryAlphabet, ListWord[getNextIndexElementWord][0]);
                if (nextIndexFoundCharacter < indexFoundCharacter) {
                    return false;
                }
                if (nextIndexFoundCharacter== indexFoundCharacter &&(ListWord[i].Length> ListWord[i+1]?.Length) ) {
                    return false;
                }
            }
            return true;
        }
        public int isCharacterInDiccionary(string Diccionary,char character) {
            if (character==null) {
                return -1;
            }
            return Diccionary.IndexOf(character);
        }
```   public bool DiccionaryAlien(List\<string> ListWord, string DiccionaryAlphabet) {

&#x20;           for (int i = 0; i < ListWord.Count(); i++) {

&#x20;               char characterFirstWord = ListWord\[i]\[0];

&#x20;               int indexFoundCharacter = isCharacterInDiccionary(DiccionaryAlphabet, characterFirstWord);

&#x20;               if (indexFoundCharacter==-1) {

&#x20;                   return false;

&#x20;               }

&#x20;               int getNextIndexElementWord= i+1;

&#x20;               if (ListWord.Count()== getNextIndexElementWord) {

&#x20;                   break;

&#x20;               }

&#x20;               int nextIndexFoundCharacter = isCharacterInDiccionary(DiccionaryAlphabet, ListWord\[getNextIndexElementWord]\[0]);

&#x20;               if (nextIndexFoundCharacter < indexFoundCharacter) {

&#x20;                   return false;

&#x20;               }

&#x20;               if (nextIndexFoundCharacter== indexFoundCharacter &&(ListWord\[i].Length> ListWord\[i+1]?.Length) ) {

&#x20;                   return false;

&#x20;               }

&#x20;           }

&#x20;           return true;

&#x20;       }

&#x20;       public int isCharacterInDiccionary(string Diccionary,char character) {

&#x20;           if (character==null) {

&#x20;               return -1;

&#x20;           }

&#x20;           return Diccionary.IndexOf(character);

&#x20;       }

franklin yancoba

student•

adjunto mi solucion en c#, ahora si a observar comno se haria correctamente :b

   public bool DiccionaryAlien(List<string> ListWord, string DiccionaryAlphabet) {
            for (int i = 0; i < ListWord.Count(); i++) {
                char characterFirstWord = ListWord[i][0];
                int indexFoundCharacter = isCharacterInDiccionary(DiccionaryAlphabet, characterFirstWord);
                if (indexFoundCharacter==-1) {
                    return false;
                }
                int getNextIndexElementWord= i+1;
                if (ListWord.Count()== getNextIndexElementWord) {
                    break;
                }
                int nextIndexFoundCharacter = isCharacterInDiccionary(DiccionaryAlphabet, ListWord[getNextIndexElementWord][0]);
                if (nextIndexFoundCharacter < indexFoundCharacter) {
                    return false;
                }
                if (nextIndexFoundCharacter== indexFoundCharacter &&(ListWord[i].Length> ListWord[i+1]?.Length) ) {
                    return false;
                }
            }
            return true;
        }
        public int isCharacterInDiccionary(string Diccionary,char character) {
            if (character==null) {
                return -1;
            }
            return Diccionary.IndexOf(character);
        }
```   public bool DiccionaryAlien(List\<string> ListWord, string DiccionaryAlphabet) {

&#x20;           for (int i = 0; i < ListWord.Count(); i++) {

&#x20;               char characterFirstWord = ListWord\[i]\[0];

&#x20;               int indexFoundCharacter = isCharacterInDiccionary(DiccionaryAlphabet, characterFirstWord);

&#x20;               if (indexFoundCharacter==-1) {

&#x20;                   return false;

&#x20;               }

&#x20;               int getNextIndexElementWord= i+1;

&#x20;               if (ListWord.Count()== getNextIndexElementWord) {

&#x20;                   break;

&#x20;               }

&#x20;               int nextIndexFoundCharacter = isCharacterInDiccionary(DiccionaryAlphabet, ListWord\[getNextIndexElementWord]\[0]);

&#x20;               if (nextIndexFoundCharacter < indexFoundCharacter) {

&#x20;                   return false;

&#x20;               }

&#x20;               if (nextIndexFoundCharacter== indexFoundCharacter &&(ListWord\[i].Length> ListWord\[i+1]?.Length) ) {

&#x20;                   return false;

&#x20;               }

&#x20;           }

&#x20;           return true;

&#x20;       }

&#x20;       public int isCharacterInDiccionary(string Diccionary,char character) {

&#x20;           if (character==null) {

&#x20;               return -1;

&#x20;           }

&#x20;           return Diccionary.IndexOf(character);

&#x20;       }

Nicolas Alpargatero

student•

Sinceramente me apoye de Copilot 🙆‍♂️ pero al forzarme comprendí mejor otro uso que se le puede dar al zip, y al else después de un for.

Milton Castañeda

student•

Esta es mi solución en Java:

Main.java

import java.util.*;

public class Main {

    private static boolean verifyingAlienDictionary(String[] words, String order) {

        int nWords = words.length;
        // direct response
        if (nWords == 0 || (nWords == 1 && words[0].length() == 0)) {
           return false;
        }

        if (nWords == 1) {
            return true;
        }

        // index
        int a1 = 0;
        int a2 = 1;
        HashMap<Character, Integer> alphabeth = new HashMap<>();
        int nAlphabeth = order.length();
        char[] arrOrder = order.toCharArray();

        for (int i = 0; i < nAlphabeth; i++) {
            alphabeth.put(arrOrder[i], i);
        }

        while (a2 < nWords) {

            char[] arrA1 = words[a1].toLowerCase().toCharArray();
            char[] arrA2 = words[a2].toLowerCase().toCharArray();

            int max = Math.min(arrA1.length, arrA2.length);

            for (int i = 0; i < max; i++) {

                int valueOrderA1 = alphabeth.get(arrA1[i]) == null ? 0 : alphabeth.get(arrA1[i]);
                int valueOrderA2 = alphabeth.get(arrA2[i]) == null ? 0 : alphabeth.get(arrA2[i]);

                // the alphabet mustn't have numbers
                if (valueOrderA1 == 0 || valueOrderA2 == 0) {
                    return false;
                }
                // the words haven't a good order
                if (valueOrderA1 > valueOrderA2) {
                    return false;
                }
                // the words have a good order
                if (valueOrderA1 < valueOrderA2) {
                    break;
                }
            }

            a1++;
            a2++;
        }

        return true;
    }

    public static void main(String[] args) {

        // input
        String order = "hlabcdefgijkmnopqrstuvwxyz";

        // input words case | empty 
        String[] wordsEmpty = { ""};
        String[] wordsEmpty2 = { };
        // input words case | one word 
        String[] words0 = { "one"};
        // input words case | true with repeat pathern
        String[] words = { "cono", "conocer" };
   
        // input words case | false
        String[] words1 = { "cono", "Amanecer" };
        // input words | case true
        String[] words2 = { "Amanecer", "Burro", "Cabra" };
        // input words | case true with repeat words
        String[] words3 = { "Amanecer", "Amanecer", "Amanecer" };
        // input words | case true with numbers
        String[] words4 = { "Amanecer1", "Amanecer2", "Amanecer3" };
        String[] words5 = { "1Amanecer1", "2Amanecer2", "2Amanecer3" };

         System.out.println("The list {\"\"} have ordered with alien dictionary | pass test [ "
                + (verifyingAlienDictionary(wordsEmpty, order) == false) + "] ");
        System.out.println("The list {} have ordered with alien dictionary | pass test [ "
                + (verifyingAlienDictionary(wordsEmpty2, order) == false) +" ]");
                
        System.out.println("The list { \"one\" } have ordered with alien dictionary | pass test [  "
                + (verifyingAlienDictionary(words0, order) == true)+" ]");
        System.out.println("The list {\"cono\",\"Conocer\"} have ordered with alien dictionary | pass test [ "
                + (verifyingAlienDictionary(words, order) == true) +" ]");
        System.out.println("The list {\"cono\",\"Amanecer\"} have ordered with alien dictionary | pass test [ "
                + (verifyingAlienDictionary(words1, order) == false) + " ] ");
        System.out.println("The list {\"Amanecer\", \"Burro\", \"Cabra\"} have ordered with alien dictionary | pass test [ "
                + (verifyingAlienDictionary(words2, order) == true) + " ]");
        System.out.println("The list {\"Amanecer\", \"Amanecer\", \"Amanecer\"} have ordered with alien dictionary | pass test [ "
                + (verifyingAlienDictionary(words3, order) == true) + " ]");
        System.out.println("The list {\"Amanecer1\", \"Amanecer2\", \"Amanecer3\"} have ordered with alien dictionary | pass test [ "
                + (verifyingAlienDictionary(words4, order) == false) + " ]");
        System.out
                .println(
                        "The list {\"1Amanecer1\", \"2Amanecer2\", \"2Amanecer3\"} have ordered with alien dictionary | pass test [ "
                                + (verifyingAlienDictionary(words5, order) == false) + " ] ");

        System.out
                .println(
                        "The list {\"1Amanecer1\", \"5Amanecer5\", \"2Amanecer3\"} have ordered with alien dictionary | pass test [ "
                                + (verifyingAlienDictionary(words5, order) == false) + " ] ");

    }
}

Carlos Raúl Romero Martínez

student•

Esta es mi soucion en c++, su complejidad es O(NM), donde N es la cantidad de cadenas y M la longitud de la cadena, guardo todas las cadenas en un array, despues voy comparanado de 1 a n-1 con la cadena anterior si es menor, si en algun momento no se cumple retorna falso y se termna el programa, lo que hago es que voy comprando dos cadenas adyacentes caractcter por caracter, como es posible que las cadenas no tengan la misma logitud comparo en base a la mas pequeña, comparo en base al alfabeto si la que es se supone que es menor su caracter esta antes en el alfabeto entonces es menor, si las cadenas son iguales retorna verdadero, si existe el caso de que las cadenas son "a" y "aa" o similares la cadena "aa" es lexicograficamente mayor, estoy asumiendo que todas las cadenas solo constan de letras minusculas.

#include<bits/stdc++.h>

using namespace std;

vector<string>palabras;

string cadena,
    alfabeto;

bool estan_ordenadas = true;

bool es_menor(char menor,char mayor){
    for(int i=0;i<alfabeto.size();i++){
        if(alfabeto[i]==menor){
            return true;
        }
        if(alfabeto[i]==mayor){
            break;
        }
    }
    return false;
}

bool cadena_odenada(string valorMayor,string valorMenor){

    int ciclo = min(valorMenor.size(),valorMayor.size());

    for(int i=0;i<ciclo;i++){
        char menor = valorMenor[i],
            mayor = valorMayor[i];
        if (menor == mayor){
            continue;
        }
        if(es_menor(menor,mayor)){
            return true;
        }
        else{
            return false;
        }
    }
    return valorMayor.size()>=valorMenor.size();
}

int main(){
    freopen("entrada.txt", "r", stdin);
    freopen("salida.txt", "w", stdout);
    while(cin>>cadena){
        if(cadena == "0"){
            break;
        }
        palabras.push_back(cadena);
    }
    cin>>alfabeto;
    for(int i=1;i<palabras.size();i++){
        if(!cadena_odenada(palabras[i],palabras[i-1])){
            estan_ordenadas = false;
            break;
        }
    }

    if(estan_ordenadas){
        cout<<"Estan ordenadas"<<endl;
    }
    else{
        cout<<"No estan ordenadas"<<endl;
    }

    return 0;
}

#caso de prueba 1

conocer cono 0 abcdefghijkImnopgrstuvwxyz

Respuesta No estan ordenadas

#caso de prueba 2 habito hacer lectura sonreir 0 hlabcdefgijkmnopqrstuvwxyz respuesta Estan ordenadas