Playground: Verifying Alien Dictionary

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

Contenido del curso

Introducción

Dos Apuntadores

Ventana Deslizante

Búsqueda Binaria

Próximos pasos

35
Estructuras de Datos Lineales: Conceptos y Aplicaciones
00:36 min

Tomar examen

Comentarios

Gabriel Revelo

student•

talvez hay una api de hackerrank o leetcode, para esto? para tener más opciones de lenguajes de programación, esque solo sé python :'(

David Alejandro Sequera Lievano

student•

Si no estoy mal platzi esta trabajando en eso para implementar su propia herramienta para testear codigo no solo en js

Miguel Angel Reyes Moreno

student•

Dile a Chat GPT que transforme tu código de Python a JavaScript y listo

Ángel Vargas Casavantes

student•

Comparto mi solución :]

export function isAlienSorted(words, order) {
	const orderMap = new Map();
	let pointer = 0; // Apuntador a palabra inicial y siguiente

	for (let i in order) // Llenamos Map de letras
		orderMap.set(order[i], i);

	while (pointer + 1 < words.length) {
		const word_1 = words[pointer];
		const word_2 = words[pointer + 1];
		let count = 0;

		console.log(word_1, word_2);

		while (count < word_1.length || count < word_2.length) {
			const charVal_1 = orderMap.get(word_1[count]);
			const charVal_2 = orderMap.get(word_2[count]);

			console.log(charVal_1, charVal_2);

			if (charVal_1 !== charVal_2) {
				if (!charVal_1)  // Si charVal_1 es undefined, sabemos que la primera palabra es mas corta
					break;

				if (charVal_1 < charVal_2) // Si charVal_1 es menor a charVal_2, rompemos ciclo
					break;

				return false;
			}

			count++;
		}

		pointer++;
	}

	return true;
}

Frandel Corporan Rodríguez

student•

Que buena solucion crack!

Juan Esteban

student•

Se hizo lo que se pudo

export function isAlienSorted(palabras, orden) {
  // Escribe tu código aquí 👈
  const dictMap = new Map();
  for (let i = 0; i < orden.length; i++) {
    dictMap.set(orden[i], i + 1)
  }
  for (let i = 0; i < palabras.length - 1; i++) {
    let actual = palabras[i]
    let siguiente = palabras[i + 1]
    let size = actual.length >= siguiente.length ? siguiente.length : actual.length
    for (let j = 0; j < size; j++) {
      let actual_char = actual[j]
      let siguiente_char = siguiente[j]
      if (actual_char == siguiente_char) {
        if (j == size - 1 && actual.length > siguiente.length) {
          return false
        }
        continue
      } else if (dictMap.get(actual_char) > dictMap.get(siguiente_char)) {
        return false
      } else if (dictMap.get(actual_char) < dictMap.get(siguiente_char)) {
        break
      }
    }
  }
  return true
}

Victor Alfredo Matzar Say

student•

La letra ‘e’ no esta en el primer y segundo alfabeto, que debería pasar cuando se comparen una pareja de caracteres con una letra que no este en el alfabeto

Andrés Guerra Montoya

student•

Depende, lo puedes manejar con excepciones para que no te saque error. Aún asi no se podría saber si estan ordenadas las palabras debido a este error. En mi código yo asumí que las palabras solo van a usar letras que estan en el alfabeto, por lo que si no se cumple esta condición el código no va a funcionar.

Edison Bedoya Garcia

student•

Mi solución

export function isAlienSorted(palabras, orden) {
  const hashTable = {}
  let i = 0
  for (let letter of orden) {
    hashTable[letter] = i
    i++
  }
  
  let current = 0
  while (current < palabras.length - 1) {
    let j = 0
    while (palabras[current][j] === palabras[current + 1][j]) {
      j++
    }
    if (palabras[current + 1][j] === undefined) return false
    if (hashTable[palabras[current][j]] > hashTable[palabras[current + 1][j]]) {
      return false
    }
    current++
  }
  return true
}

REYNALDO FABIAN NORIEGA ZAMBRANO

student•

La de usar otro lenguaje de programacion no se la saben?

José López Lara

student•

Concuerdo mi buen, tan si quiera un botoncinto de alternar lenguaje, pero puedo como js corre en el navegador

Yojan Antonio Pardo Zabala

student•

Creo que los casos de prueba están mal porque en el ejemplo 1 al faltar la letra e en el alfabeto va retornar false al validar habito contra hacer

Cesar Cordova Contreras

student•

esta es mi solucion

export function isAlienSorted(palabras, orden) {

  for (let i = 0; i < palabras.length - 1; i++) {
    let current_word = palabras[i]
    let next_word = palabras[i + 1]
    let diferenciaEncontrada = false;

    for (let j = 0; j < Math.min(current_word.length, next_word.length); j++) {
      if (current_word[j] !== next_word[j]) {

        let current_word_position = orden.indexOf(current_word[j])
        let current_next_word_position = orden.indexOf(next_word[j])
        diferenciaEncontrada = true;

        // si la pocicion actual es menor a la siguiente posiscion de la letra entonces rompemos por ejemplo
        // b = 3 c = 4
        if (current_word_position < current_next_word_position) {
          break;
        } else if (current_word_position > current_next_word_position) {
          console.log('falso')
          return false
        }

      }
    }
    if (!diferenciaEncontrada && current_word.length > next_word.length) {
      console.log("falso")
      return false
    }
  }
  console.log('verdadero')
  return true
}

CRISTHIAM CAMILO MONSALVE PANTOJA

student••

Mi respuesta:

export function isAlienSorted(words, order) {
    // Creamos un mapa para buscar el orden en tiempo constante O(1)
    const orderMap = {};
    for (let i = 0; i < orden.length; i++) {
        orderMap[orden[i]] = i;
    }

    // Función auxiliar para comparar dos palabras (Aquí la lógica recursiva)
    function compareTwo(word1, word2) {
        if (word1 === word2) return true;
        if (word1 === "") return true; // La palabra corta va primero
        if (word2 === "") return false; // La palabra larga no puede ir antes que su prefijo

        const char1 = word1[0];
        const char2 = word2[0];

        if (orderMap[char1] < orderMap[char2]) return true;
        if (orderMap[char1] > orderMap[char2]) return false;

        // Si son iguales, recursión con el resto de la cadena
        return compareTwo(word1.substring(1), word2.substring(1));
    }

    // Recorremos el array de palabras comparándolas de par en par
    for (let i = 0; i < palabras.length - 1; i++) {
        if (!compareTwo(palabras[i], palabras[i + 1])) {
            return false;
        }
    }

    return true;
}

José López Lara

student•

Mi solución en Python


# alphabet = "hlabcdefgijkmnopqrstuvwxyz"
 #words = ["hlleo", "bye"]

# words = ['conocer', 'cono']
# alphabet = 'abcdfghijklmnopqrstuvwxyz'

words = ['habito', 'hacer', 'lectura', 'sonreir']
alphabet = "hlabcdefgikmnopqrstuvqxyz"

# alphabet = "abcdefghijklmnopqrstuvwxyz"
# words = ["application", "appstore"]
# words = ["fox", "apple", "app"]
# words = ["apple", "app", "fox"]
# words = ["app", "apple", "fox"]

# Process
# 1. build indexWordMap fucntion
# ----------------------------------------------------------------------------
def indexWordMap(alien_alphabet) -> list:
  alpthabetMap = {}

  for idx, word in enumerate(alien_alphabet):
    alpthabetMap[word] = idx

  return alpthabetMap




# 2. build comparateWords function
# ----------------------------------------------------------------------------
def camparateWords(wordList, alphabetMap) -> bool:

# --> DP: wordList = ["fox", "apple", "app"]

  # [O(n)] 2.1 Cycle using  two pointers pattern, initialized in [word1] and [word2]. I going to compare
  # the lexicographic letter position before continuing.
  wordListSize = len(wordList)
  
  # --> DP: wordListSize = 3

  for idxList, word in enumerate(wordList):
    # Late leave validation for stopping cycle wnen my currund word is equals tha my end word
    
    # --> DP: 0 == 2
    if(idxList == wordListSize - 1):
      return True

    # --> DP: nextWord = 1
    # --> DP: nextWordSize = 3
    # --> DP: isNextWordClippi = True
    nextWord = wordList[idxList + 1]
    nextWordSize = len(nextWord)
    isNextWordClippi =  True

    # [O(n)] 2.2 Range word pointer one letter by letter and compare the value whit the each word
    # ranging the word pointer two letter by letter at the same time.
    # --------------------------------------------------------------------------
    for idxWord, letterWord in enumerate(word):
      # --> DP: idxWord = 0
      # --> DP: letterWord = f
      
      # Late leave validation for stopping cycle when my nextWord has less number of letters
      
      # --> DP: 0 > 4 
      if(idxWord > nextWordSize - 1):
        # Validation for avoiting return True when I'm sorting "application" and "app"
        if(isNextWordClippi):
          return False        
        break

      # --> DP: positionLetterOne(6) | positionLetterTwo(1)
      positionLetterOne = alphabetMap[letterWord]
      positionLetterTwo = alphabetMap[nextWord[idxWord]]

      # Validation for avoiting return True when I'm sorting "application" and "app"
      # --> DP:isNextWordClippi = False
      if(positionLetterOne == positionLetterTwo):
        continue
      elif(isNextWordClippi):
        isNextWordClippi = False

      # 6 > 1 
      if(positionLetterOne > positionLetterTwo):
        return False
      else:
        break

alphabetMap = indexWordMap(alphabet)
isSorted =  camparateWords(words, alphabetMap)


# 3. Test 
# ----------------------------------------------------------------------------
print(isSorted)

Felipe Guzmán - Bautista

student•

El playground solo esta en JS?

Omar Daniel Centeno

student•

Para este ejercicio, sí. En algunos otros cursos también podrás encontrar la opción de resolverlo con Python. Esperamos muy pronto tener más opciones para otros lenguajes de programación.

Edwin Garcés Saucedo

student•

Esta es mi solución:

function mapDictionary(dictionary = "") {
  const dictionaryMap = new Map()
  for (let i = 0; i < dictionary.length; i++) {
    dictionaryMap.set(dictionary[i], i)
  }
  return dictionaryMap
}

function compareWords(firstWord = "", secondWord = "", dictionary = { a: 1 }) {
  const minLength = firstWord.length > secondWord.length ? firstWord.length : secondWord.length
  for (let i = 0; i < minLength; i++) {
    const firstChar = firstWord[i]
    const secondChar = secondWord[i]
    if (dictionary.get(firstChar) < dictionary.get(secondChar)) {
      return true
    } else if (dictionary.get(firstChar) > dictionary.get(secondChar)) {
      return false
    }
  }
  return false
}

export function isAlienSorted(words, dictionary) {
  const dictionaryMapped = mapDictionary(dictionary)
  for (let i = 0; i < words.length - 1; i++) {
    const currentWord = words[i];
    const nextWord = words[i + 1]
    const areInOrder = compareWords(currentWord, nextWord, dictionaryMapped)
    if (!areInOrder) {
      return false
    }
  }
  return true
}

John Eduard Meneses González

student•

my solution:

export function isAlienSorted(words, order) {
  // Paso 1: Crear un mapa de orden para una búsqueda eficiente
  const orderMap = new Map();
  for (let i = 0; i < order.length; i++) {
    orderMap.set(order[i], i);
  }

  // Paso 2: Función auxiliar para comparar dos palabras
  function compareWords(word1, word2) {
    const minLength = Math.min(word1.length, word2.length);
    
    for (let i = 0; i < minLength; i++) {
      const char1 = word1[i];
      const char2 = word2[i];
      
      if (char1 !== char2) {
        return orderMap.get(char1) - orderMap.get(char2);
      }
    }
    // Si llegamos aquí, significa que una palabra es prefijo de la otra
    return word1.length - word2.length;
  }

  // Paso 3: Comparar las palabras en el orden dado
  for (let i = 0; i < words.length - 1; i++) {
    if (compareWords(words[i], words[i + 1]) > 0) {
      return false;
    }
  }
  
  return true;
}

Carlos Hernandez

student•

const verifyAlienDictionary = (words, order) => {
    //Get order letters as list
    const orderLetters = order.split('');

    let isDictionaryOrdered = true;
    for (let i = 0; i < words.length; i++) {
        const word = words[i];
        const nextIndex = i + 1;
        if (nextIndex < words.length) {
            const nextWord = words[nextIndex];
            isDictionaryOrdered = isWordOrdered(word, nextWord, orderLetters);
            if (!isDictionaryOrdered) {
                break;
            }
        }
    }

    return isDictionaryOrdered
}

const getLetterIndex = (letter, orderLetters) => {
    return orderLetters.indexOf(letter);
};

const isWordOrdered = (word, nextWord, orderLetters) => {
    const wordsLetter = word.split('');
    const nextWordsLetter = nextWord.split('');

    const smallerLength = Math.min(wordsLetter.length, nextWordsLetter.length);

    for (let i = 0; i < smallerLength; i++) {
        const wordLetterIndex = getLetterIndex(wordsLetter[i], orderLetters);
        const nextWordLetterIndex = getLetterIndex(nextWordsLetter[i], orderLetters);

        if (wordLetterIndex > nextWordLetterIndex) {
            return false;
        } else if (wordLetterIndex < nextWordLetterIndex) {
            return true;
        }
    }

    return word.length <= nextWord.length;;
}

console.log(verifyAlienDictionary(["hello", "leetcode"], "hlabcdefgijkmnopqrstuvwxyz")); // true
console.log(verifyAlienDictionary(["conocer", "cono"], "abcdefghijklmnopqrstuvwxyz")); // false
console.log(verifyAlienDictionary(["habito", "hacer", "lectura", "sonreir"], "hlabcdefgijkmnopqrstuvwxyz")); // true
console.log(verifyAlienDictionary(["habito", "hacer", "sonreir", "lectura"], "hlabcdefgijkmnopqrstuvwxyz")); // false
```const verifyAlienDictionary = (words, order) => {    //Get order letters as list    const orderLetters = order.split('');
    let isDictionaryOrdered = true;    for (let i = 0; i < words.length; i++) {        const word = words\[i];        const nextIndex = i + 1;        if (nextIndex < words.length) {            const nextWord = words\[nextIndex];            isDictionaryOrdered = isWordOrdered(word, nextWord, orderLetters);            if (!isDictionaryOrdered) {                break;            }        }    }
    return isDictionaryOrdered}
const getLetterIndex = (letter, orderLetters) => {    return orderLetters.indexOf(letter);};
const isWordOrdered = (word, nextWord, orderLetters) => {    const wordsLetter = word.split('');    const nextWordsLetter = nextWord.split('');
    const smallerLength = Math.min(wordsLetter.length, nextWordsLetter.length);
    for (let i = 0; i < smallerLength; i++) {        const wordLetterIndex = getLetterIndex(wordsLetter\[i], orderLetters);        const nextWordLetterIndex = getLetterIndex(nextWordsLetter\[i], orderLetters);
        if (wordLetterIndex > nextWordLetterIndex) {            return false;        } else if (wordLetterIndex < nextWordLetterIndex) {            return true;        }    }
    return word.length <= nextWord.length;;}
console.log(verifyAlienDictionary(\["hello", "leetcode"], "hlabcdefgijkmnopqrstuvwxyz")); // trueconsole.log(verifyAlienDictionary(\["conocer", "cono"], "abcdefghijklmnopqrstuvwxyz")); // falseconsole.log(verifyAlienDictionary(\["habito", "hacer", "lectura", "sonreir"], "hlabcdefgijkmnopqrstuvwxyz")); // trueconsole.log(verifyAlienDictionary(\["habito", "hacer", "sonreir", "lectura"], "hlabcdefgijkmnopqrstuvwxyz")); // false

Cesar Augusto Mora Castilo

student•

La salida de la entrada uno debe ser false, la t esta después de la r en el diccionario, y hay que considerar que no existe la e en el diccionario de las dos primeras entradas.

Son los casos especiales a los que se referían en la clase por los que hay que preguntar al analizar los requerimientos del problema.

export function isAlienSorted(palabras, orden) {
  // Escribe tu código aquí 👈
  const words = palabras;
  const dict = orden;
  // crear hash table con Map
  let counter = 1;
  const hashTable = new Map();
  let ordered = true; // ¿está ordenada la lista?

  for (let s in dict) {
    hashTable.set(dict[counter - 1], counter);
    counter++;
  }

  // comparar palabras  
  for (let i = 0; i < words.length - 1; i++) {

    // si ya se detectaron dos letras en desorden no seguir
    if (!ordered) {
      break;
    }

    // obtener palabras a comparar
    let word1 = words[i];
    let word2 = words[i + 1];

    // comparar un numero de caracteres igual al de la
    // palabra mas corta
    let compare_times = 0;

    if (word1.length <= word2.length) {
      compare_times = word1.length;
    } else {
      compare_times = word2.length;
    }

    // comparar letra a letra
    let pointer = 0;
    while (pointer < compare_times - 1) {
      // La e no esta definida, por lo tanto se ignora  
      if ((hashTable.get(word1[pointer]) <= hashTable.get(word2[pointer])) ||
        hashTable.get(word1[pointer]) === undefined ||
        hashTable.get(word2[pointer]) === undefined
      ) {
        pointer++;
        if (word1.length > word2.length) {
          ordered = false;
          break; // las palabras estan en desorden
        }
      } else {
        ordered = false;
        break; // no es necesario comparar mas
      }
    }

  }
  return ordered;
}
```&#x20;

Luis Amador Marroquin Delgado

student•

Me costo entender sin embargo esta fue la solución a la que llegue comparto código:

export function isAlienSorted(palabras, orden) {
  const ordenMap = new Map()
  for (let i = 0; i < orden.length; i++) {
    ordenMap.set(orden.charAt(i), i + 1)
  }
  const compare = (palabra1, palabra2) => {
    const len = Math.min(palabra1.length, palabra2.length)
    for (let i = 0; i < len; i++) {
      const pos1 = ordenMap.get(palabra1.charAt(i))
      const pos2 = ordenMap.get(palabra2.charAt(i))
      if (pos1 < pos2) {
        return true
      } else if (pos1 > pos2) {
        return false
      }
    }
    return palabra1.length <= palabra2.length
  }

  for (let i = 0; i < palabras.length - 1; i++){
    if (!compare(palabras[i], palabras[i + 1])) {
      return false
    }
  }
  return true
}

Leonardo Bazán Márquez

student•

En el primer y segundo abecedario no existe la letra e y se supone que el primero resulte en true

Julian Castro

student•

Lo mas corto que pude :(

export function isAlienSorted(palabras, orden) {
  const orderMap = new Map();
  for (let i = 0; i < orden.length; i++) {
    orderMap.set(orden[i], i);
  }

  for (let i = 0; i < palabras.length; i++) {
    if (i + 1 === palabras.length) break;

    const currentWord = palabras[i];
    const nextWord = palabras[i + 1];
    const maxWordSize = currentWord.length > nextWord.length ?
      currentWord.length : nextWord.length;

    for (let j = 0; j < maxWordSize; j++) {
      let currentWordLexValue = orderMap.get(currentWord[j]);
      let nextWordLexValue = orderMap.get(nextWord[j]);

      if (currentWordLexValue === undefined) currentWordLexValue = -1;
      if (nextWordLexValue === undefined) nextWordLexValue = -1;

      if (currentWordLexValue < nextWordLexValue) break;
      else if (currentWordLexValue > nextWordLexValue) return false;
    }
  }

  return true;
}

Noldia Chavez Cavero

student•

Mi aporte en java:


import java.util.Hashtable;

import java.util.stream.IntStream;



public class VerifyingAlienDictionary {



&#x20;   private boolean isInAlienOrder(String word1, String word2, Hashtable\<Character, Integer> orderMap) {

&#x20;       int len1 = word1.length();

&#x20;       int len2 = word2.length();

&#x20;       int minLen = Math.min(len1, len2);



&#x20;       for (int i = 0; i < minLen; i++) {

&#x20;           char char1 = word1.charAt(i);

&#x20;           char char2 = word2.charAt(i);



&#x20;           if (char1 != char2) {

&#x20;               return orderMap.get(char1) < orderMap.get(char2);

&#x20;           }

&#x20;       }



&#x20;       return len1 <= len2;

&#x20;   }



&#x20;   public boolean verifying(String\[] words, String alphabetOrder) {

&#x20;       Hashtable\<Character, Integer> order = new Hashtable\<Character, Integer>();

&#x20;       IntStream.range(0, alphabetOrder.length())

&#x20;               .forEach( i -> {

&#x20;                   order.put(alphabetOrder.charAt(i), i);

&#x20;               });

&#x20;       return IntStream.range( 0, words.length - 1 )

&#x20;               .allMatch(i -> isInAlienOrder(words\[i], words\[i+1], order) );

&#x20;   }

}

Noldia Chavez Cavero

student•

Mi aporte con hecho en java:


import java.util.Hashtable;
import java.util.stream.IntStream;
public class VerifyingAlienDictionary {

&#x20;   private boolean isInAlienOrder(String word1, String word2, Hashtable\<Character, Integer> orderMap) {
&#x20;       int len1 = word1.length();
&#x20;       int len2 = word2.length();
&#x20;       int minLen = Math.*min*(len1, len2);
&#x20;       for (int i = 0; i < minLen; i++) {
&#x20;           char char1 = word1.charAt(i);
&#x20;           char char2 = word2.charAt(i);
&#x20;           if (char1 != char2) {
&#x20;               return orderMap.get(char1) < orderMap.get(char2);
&#x20;           }
&#x20;       }

&#x20;       return len1 <= len2;
&#x20;   }

&#x20;   public boolean verifying(String\[] words, String alphabetOrder) {
&#x20;       Hashtable\<Character, Integer> order = new Hashtable\<Character, Integer>();
&#x20;       IntStream.*range*(0, alphabetOrder.length())
&#x20;               .forEach( i -> {
&#x20;                   order.put(alphabetOrder.charAt(i), i);
&#x20;               });
&#x20;       return IntStream.*range*( 0, words.length - 1 )
&#x20;               .allMatch(i -> isInAlienOrder(words\[i], words\[i+1], order) );
&#x20;   }
}

export function isAlienSorted(words, order) {
	const orderMap = new Map();
	let pointer = 0; // Apuntador a palabra inicial y siguiente

	for (let i in order) // Llenamos Map de letras
		orderMap.set(order[i], i);

	while (pointer + 1 < words.length) {
		const word_1 = words[pointer];
		const word_2 = words[pointer + 1];
		let count = 0;

		console.log(word_1, word_2);

		while (count < word_1.length || count < word_2.length) {
			const charVal_1 = orderMap.get(word_1[count]);
			const charVal_2 = orderMap.get(word_2[count]);

			console.log(charVal_1, charVal_2);

			if (charVal_1 !== charVal_2) {
				if (!charVal_1)  // Si charVal_1 es undefined, sabemos que la primera palabra es mas corta
					break;

				if (charVal_1 < charVal_2) // Si charVal_1 es menor a charVal_2, rompemos ciclo
					break;

				return false;
			}

			count++;
		}

		pointer++;
	}

	return true;
}

export function isAlienSorted(palabras, orden) {
  // Escribe tu código aquí 👈
  const dictMap = new Map();
  for (let i = 0; i < orden.length; i++) {
    dictMap.set(orden[i], i + 1)
  }
  for (let i = 0; i < palabras.length - 1; i++) {
    let actual = palabras[i]
    let siguiente = palabras[i + 1]
    let size = actual.length >= siguiente.length ? siguiente.length : actual.length
    for (let j = 0; j < size; j++) {
      let actual_char = actual[j]
      let siguiente_char = siguiente[j]
      if (actual_char == siguiente_char) {
        if (j == size - 1 && actual.length > siguiente.length) {
          return false
        }
        continue
      } else if (dictMap.get(actual_char) > dictMap.get(siguiente_char)) {
        return false
      } else if (dictMap.get(actual_char) < dictMap.get(siguiente_char)) {
        break
      }
    }
  }
  return true
} 

export function isAlienSorted(palabras, orden) {
  const hashTable = {}
  let i = 0
  for (let letter of orden) {
    hashTable[letter] = i
    i++
  }
  
  let current = 0
  while (current < palabras.length - 1) {
    let j = 0
    while (palabras[current][j] === palabras[current + 1][j]) {
      j++
    }
    if (palabras[current + 1][j] === undefined) return false
    if (hashTable[palabras[current][j]] > hashTable[palabras[current + 1][j]]) {
      return false
    }
    current++
  }
  return true
}

export function isAlienSorted(palabras, orden) {

  for (let i = 0; i < palabras.length - 1; i++) {
    let current_word = palabras[i]
    let next_word = palabras[i + 1]
    let diferenciaEncontrada = false;

    for (let j = 0; j < Math.min(current_word.length, next_word.length); j++) {
      if (current_word[j] !== next_word[j]) {

        let current_word_position = orden.indexOf(current_word[j])
        let current_next_word_position = orden.indexOf(next_word[j])
        diferenciaEncontrada = true;

        // si la pocicion actual es menor a la siguiente posiscion de la letra entonces rompemos por ejemplo
        // b = 3 c = 4
        if (current_word_position < current_next_word_position) {
          break;
        } else if (current_word_position > current_next_word_position) {
          console.log('falso')
          return false
        }

      }
    }
    if (!diferenciaEncontrada && current_word.length > next_word.length) {
      console.log("falso")
      return false
    }
  }
  console.log('verdadero')
  return true
}

export function isAlienSorted(words, order) {
    // Creamos un mapa para buscar el orden en tiempo constante O(1)
    const orderMap = {};
    for (let i = 0; i < orden.length; i++) {
        orderMap[orden[i]] = i;
    }

    // Función auxiliar para comparar dos palabras (Aquí la lógica recursiva)
    function compareTwo(word1, word2) {
        if (word1 === word2) return true;
        if (word1 === "") return true; // La palabra corta va primero
        if (word2 === "") return false; // La palabra larga no puede ir antes que su prefijo

        const char1 = word1[0];
        const char2 = word2[0];

        if (orderMap[char1] < orderMap[char2]) return true;
        if (orderMap[char1] > orderMap[char2]) return false;

        // Si son iguales, recursión con el resto de la cadena
        return compareTwo(word1.substring(1), word2.substring(1));
    }

    // Recorremos el array de palabras comparándolas de par en par
    for (let i = 0; i < palabras.length - 1; i++) {
        if (!compareTwo(palabras[i], palabras[i + 1])) {
            return false;
        }
    }

    return true;
}

# alphabet = "hlabcdefgijkmnopqrstuvwxyz"
 #words = ["hlleo", "bye"]

# words = ['conocer', 'cono']
# alphabet = 'abcdfghijklmnopqrstuvwxyz'

words = ['habito', 'hacer', 'lectura', 'sonreir']
alphabet = "hlabcdefgikmnopqrstuvqxyz"

# alphabet = "abcdefghijklmnopqrstuvwxyz"
# words = ["application", "appstore"]
# words = ["fox", "apple", "app"]
# words = ["apple", "app", "fox"]
# words = ["app", "apple", "fox"]

# Process
# 1. build indexWordMap fucntion
# ----------------------------------------------------------------------------
def indexWordMap(alien_alphabet) -> list:
  alpthabetMap = {}

  for idx, word in enumerate(alien_alphabet):
    alpthabetMap[word] = idx

  return alpthabetMap




# 2. build comparateWords function
# ----------------------------------------------------------------------------
def camparateWords(wordList, alphabetMap) -> bool:

# --> DP: wordList = ["fox", "apple", "app"]

  # [O(n)] 2.1 Cycle using  two pointers pattern, initialized in [word1] and [word2]. I going to compare
  # the lexicographic letter position before continuing.
  wordListSize = len(wordList)
  
  # --> DP: wordListSize = 3

  for idxList, word in enumerate(wordList):
    # Late leave validation for stopping cycle wnen my currund word is equals tha my end word
    
    # --> DP: 0 == 2
    if(idxList == wordListSize - 1):
      return True

    # --> DP: nextWord = 1
    # --> DP: nextWordSize = 3
    # --> DP: isNextWordClippi = True
    nextWord = wordList[idxList + 1]
    nextWordSize = len(nextWord)
    isNextWordClippi =  True

    # [O(n)] 2.2 Range word pointer one letter by letter and compare the value whit the each word
    # ranging the word pointer two letter by letter at the same time.
    # --------------------------------------------------------------------------
    for idxWord, letterWord in enumerate(word):
      # --> DP: idxWord = 0
      # --> DP: letterWord = f
      
      # Late leave validation for stopping cycle when my nextWord has less number of letters
      
      # --> DP: 0 > 4 
      if(idxWord > nextWordSize - 1):
        # Validation for avoiting return True when I'm sorting "application" and "app"
        if(isNextWordClippi):
          return False        
        break

      # --> DP: positionLetterOne(6) | positionLetterTwo(1)
      positionLetterOne = alphabetMap[letterWord]
      positionLetterTwo = alphabetMap[nextWord[idxWord]]

      # Validation for avoiting return True when I'm sorting "application" and "app"
      # --> DP:isNextWordClippi = False
      if(positionLetterOne == positionLetterTwo):
        continue
      elif(isNextWordClippi):
        isNextWordClippi = False

      # 6 > 1 
      if(positionLetterOne > positionLetterTwo):
        return False
      else:
        break

alphabetMap = indexWordMap(alphabet)
isSorted =  camparateWords(words, alphabetMap)


# 3. Test 
# ----------------------------------------------------------------------------
print(isSorted)

function mapDictionary(dictionary = "") {
  const dictionaryMap = new Map()
  for (let i = 0; i < dictionary.length; i++) {
    dictionaryMap.set(dictionary[i], i)
  }
  return dictionaryMap
}

function compareWords(firstWord = "", secondWord = "", dictionary = { a: 1 }) {
  const minLength = firstWord.length > secondWord.length ? firstWord.length : secondWord.length
  for (let i = 0; i < minLength; i++) {
    const firstChar = firstWord[i]
    const secondChar = secondWord[i]
    if (dictionary.get(firstChar) < dictionary.get(secondChar)) {
      return true
    } else if (dictionary.get(firstChar) > dictionary.get(secondChar)) {
      return false
    }
  }
  return false
}

export function isAlienSorted(words, dictionary) {
  const dictionaryMapped = mapDictionary(dictionary)
  for (let i = 0; i < words.length - 1; i++) {
    const currentWord = words[i];
    const nextWord = words[i + 1]
    const areInOrder = compareWords(currentWord, nextWord, dictionaryMapped)
    if (!areInOrder) {
      return false
    }
  }
  return true
}

export function isAlienSorted(words, order) {
  // Paso 1: Crear un mapa de orden para una búsqueda eficiente
  const orderMap = new Map();
  for (let i = 0; i < order.length; i++) {
    orderMap.set(order[i], i);
  }

  // Paso 2: Función auxiliar para comparar dos palabras
  function compareWords(word1, word2) {
    const minLength = Math.min(word1.length, word2.length);
    
    for (let i = 0; i < minLength; i++) {
      const char1 = word1[i];
      const char2 = word2[i];
      
      if (char1 !== char2) {
        return orderMap.get(char1) - orderMap.get(char2);
      }
    }
    // Si llegamos aquí, significa que una palabra es prefijo de la otra
    return word1.length - word2.length;
  }

  // Paso 3: Comparar las palabras en el orden dado
  for (let i = 0; i < words.length - 1; i++) {
    if (compareWords(words[i], words[i + 1]) > 0) {
      return false;
    }
  }
  
  return true;
}

const verifyAlienDictionary = (words, order) => {
    //Get order letters as list
    const orderLetters = order.split('');

    let isDictionaryOrdered = true;
    for (let i = 0; i < words.length; i++) {
        const word = words[i];
        const nextIndex = i + 1;
        if (nextIndex < words.length) {
            const nextWord = words[nextIndex];
            isDictionaryOrdered = isWordOrdered(word, nextWord, orderLetters);
            if (!isDictionaryOrdered) {
                break;
            }
        }
    }

    return isDictionaryOrdered
}

const getLetterIndex = (letter, orderLetters) => {
    return orderLetters.indexOf(letter);
};

const isWordOrdered = (word, nextWord, orderLetters) => {
    const wordsLetter = word.split('');
    const nextWordsLetter = nextWord.split('');

    const smallerLength = Math.min(wordsLetter.length, nextWordsLetter.length);

    for (let i = 0; i < smallerLength; i++) {
        const wordLetterIndex = getLetterIndex(wordsLetter[i], orderLetters);
        const nextWordLetterIndex = getLetterIndex(nextWordsLetter[i], orderLetters);

        if (wordLetterIndex > nextWordLetterIndex) {
            return false;
        } else if (wordLetterIndex < nextWordLetterIndex) {
            return true;
        }
    }

    return word.length <= nextWord.length;;
}

console.log(verifyAlienDictionary(["hello", "leetcode"], "hlabcdefgijkmnopqrstuvwxyz")); // true
console.log(verifyAlienDictionary(["conocer", "cono"], "abcdefghijklmnopqrstuvwxyz")); // false
console.log(verifyAlienDictionary(["habito", "hacer", "lectura", "sonreir"], "hlabcdefgijkmnopqrstuvwxyz")); // true
console.log(verifyAlienDictionary(["habito", "hacer", "sonreir", "lectura"], "hlabcdefgijkmnopqrstuvwxyz")); // false
```const verifyAlienDictionary = (words, order) => {    //Get order letters as list    const orderLetters = order.split('');
    let isDictionaryOrdered = true;    for (let i = 0; i < words.length; i++) {        const word = words\[i];        const nextIndex = i + 1;        if (nextIndex < words.length) {            const nextWord = words\[nextIndex];            isDictionaryOrdered = isWordOrdered(word, nextWord, orderLetters);            if (!isDictionaryOrdered) {                break;            }        }    }
    return isDictionaryOrdered}
const getLetterIndex = (letter, orderLetters) => {    return orderLetters.indexOf(letter);};
const isWordOrdered = (word, nextWord, orderLetters) => {    const wordsLetter = word.split('');    const nextWordsLetter = nextWord.split('');
    const smallerLength = Math.min(wordsLetter.length, nextWordsLetter.length);
    for (let i = 0; i < smallerLength; i++) {        const wordLetterIndex = getLetterIndex(wordsLetter\[i], orderLetters);        const nextWordLetterIndex = getLetterIndex(nextWordsLetter\[i], orderLetters);
        if (wordLetterIndex > nextWordLetterIndex) {            return false;        } else if (wordLetterIndex < nextWordLetterIndex) {            return true;        }    }
    return word.length <= nextWord.length;;}
console.log(verifyAlienDictionary(\["hello", "leetcode"], "hlabcdefgijkmnopqrstuvwxyz")); // trueconsole.log(verifyAlienDictionary(\["conocer", "cono"], "abcdefghijklmnopqrstuvwxyz")); // falseconsole.log(verifyAlienDictionary(\["habito", "hacer", "lectura", "sonreir"], "hlabcdefgijkmnopqrstuvwxyz")); // trueconsole.log(verifyAlienDictionary(\["habito", "hacer", "sonreir", "lectura"], "hlabcdefgijkmnopqrstuvwxyz")); // false

export function isAlienSorted(palabras, orden) {
  // Escribe tu código aquí 👈
  const words = palabras;
  const dict = orden;
  // crear hash table con Map
  let counter = 1;
  const hashTable = new Map();
  let ordered = true; // ¿está ordenada la lista?

  for (let s in dict) {
    hashTable.set(dict[counter - 1], counter);
    counter++;
  }

  // comparar palabras  
  for (let i = 0; i < words.length - 1; i++) {

    // si ya se detectaron dos letras en desorden no seguir
    if (!ordered) {
      break;
    }

    // obtener palabras a comparar
    let word1 = words[i];
    let word2 = words[i + 1];

    // comparar un numero de caracteres igual al de la
    // palabra mas corta
    let compare_times = 0;

    if (word1.length <= word2.length) {
      compare_times = word1.length;
    } else {
      compare_times = word2.length;
    }

    // comparar letra a letra
    let pointer = 0;
    while (pointer < compare_times - 1) {
      // La e no esta definida, por lo tanto se ignora  
      if ((hashTable.get(word1[pointer]) <= hashTable.get(word2[pointer])) ||
        hashTable.get(word1[pointer]) === undefined ||
        hashTable.get(word2[pointer]) === undefined
      ) {
        pointer++;
        if (word1.length > word2.length) {
          ordered = false;
          break; // las palabras estan en desorden
        }
      } else {
        ordered = false;
        break; // no es necesario comparar mas
      }
    }

  }
  return ordered;
}
```&#x20;

export function isAlienSorted(palabras, orden) {
  const ordenMap = new Map()
  for (let i = 0; i < orden.length; i++) {
    ordenMap.set(orden.charAt(i), i + 1)
  }
  const compare = (palabra1, palabra2) => {
    const len = Math.min(palabra1.length, palabra2.length)
    for (let i = 0; i < len; i++) {
      const pos1 = ordenMap.get(palabra1.charAt(i))
      const pos2 = ordenMap.get(palabra2.charAt(i))
      if (pos1 < pos2) {
        return true
      } else if (pos1 > pos2) {
        return false
      }
    }
    return palabra1.length <= palabra2.length
  }

  for (let i = 0; i < palabras.length - 1; i++){
    if (!compare(palabras[i], palabras[i + 1])) {
      return false
    }
  }
  return true
}

export function isAlienSorted(palabras, orden) {
  const orderMap = new Map();
  for (let i = 0; i < orden.length; i++) {
    orderMap.set(orden[i], i);
  }

  for (let i = 0; i < palabras.length; i++) {
    if (i + 1 === palabras.length) break;

    const currentWord = palabras[i];
    const nextWord = palabras[i + 1];
    const maxWordSize = currentWord.length > nextWord.length ?
      currentWord.length : nextWord.length;

    for (let j = 0; j < maxWordSize; j++) {
      let currentWordLexValue = orderMap.get(currentWord[j]);
      let nextWordLexValue = orderMap.get(nextWord[j]);

      if (currentWordLexValue === undefined) currentWordLexValue = -1;
      if (nextWordLexValue === undefined) nextWordLexValue = -1;

      if (currentWordLexValue < nextWordLexValue) break;
      else if (currentWordLexValue > nextWordLexValue) return false;
    }
  }

  return true;
}

import java.util.Hashtable;

import java.util.stream.IntStream;

public class VerifyingAlienDictionary {

&#x20;   private boolean isInAlienOrder(String word1, String word2, Hashtable\<Character, Integer> orderMap) {

&#x20;       int len1 = word1.length();

&#x20;       int len2 = word2.length();

&#x20;       int minLen = Math.min(len1, len2);

&#x20;       for (int i = 0; i < minLen; i++) {

&#x20;           char char1 = word1.charAt(i);

&#x20;           char char2 = word2.charAt(i);

&#x20;           if (char1 != char2) {

&#x20;               return orderMap.get(char1) < orderMap.get(char2);

&#x20;           }

&#x20;       }

&#x20;       return len1 <= len2;

&#x20;   }

&#x20;   public boolean verifying(String\[] words, String alphabetOrder) {

&#x20;       Hashtable\<Character, Integer> order = new Hashtable\<Character, Integer>();

&#x20;       IntStream.range(0, alphabetOrder.length())

&#x20;               .forEach( i -> {

&#x20;                   order.put(alphabetOrder.charAt(i), i);

&#x20;               });

&#x20;       return IntStream.range( 0, words.length - 1 )

&#x20;               .allMatch(i -> isInAlienOrder(words\[i], words\[i+1], order) );

&#x20;   }

}

import java.util.Hashtable;
import java.util.stream.IntStream;
public class VerifyingAlienDictionary {

&#x20;   private boolean isInAlienOrder(String word1, String word2, Hashtable\<Character, Integer> orderMap) {
&#x20;       int len1 = word1.length();
&#x20;       int len2 = word2.length();
&#x20;       int minLen = Math.*min*(len1, len2);
&#x20;       for (int i = 0; i < minLen; i++) {
&#x20;           char char1 = word1.charAt(i);
&#x20;           char char2 = word2.charAt(i);
&#x20;           if (char1 != char2) {
&#x20;               return orderMap.get(char1) < orderMap.get(char2);
&#x20;           }
&#x20;       }

&#x20;       return len1 <= len2;
&#x20;   }

&#x20;   public boolean verifying(String\[] words, String alphabetOrder) {
&#x20;       Hashtable\<Character, Integer> order = new Hashtable\<Character, Integer>();
&#x20;       IntStream.*range*(0, alphabetOrder.length())
&#x20;               .forEach( i -> {
&#x20;                   order.put(alphabetOrder.charAt(i), i);
&#x20;               });
&#x20;       return IntStream.*range*( 0, words.length - 1 )
&#x20;               .allMatch(i -> isInAlienOrder(words\[i], words\[i+1], order) );
&#x20;   }
}

Playground: Verifying Alien Dictionary

Introducción

Patrones de Arreglos y Strings: Ventana Deslizante y Dos Apuntadores

Arrays y Strings: Funcionamiento y Complejidades Temporales

Dos Apuntadores

Patrón de Dos Apuntadores en Algoritmos de Lista

Verificación de Orden en Diccionario Alienígena

Ordenamiento de Palabras en Idiomas Alienígenas