Publicado el

Desenredando el desafío de los caracteres comunes: Un cuento de TypeScript

Autores

Repositorio de GitHub: https://github.com/ImBIOS/common-char-extractor-ts

En el ámbito de las entrevistas de codificación, los desafíos algorítmicos no solo sirven como pruebas del conocimiento técnico, sino que también son una ventana al ingenio para resolver problemas de los candidatos. Un problema tan intrigante, que se encuentra a menudo, gira en torno a la manipulación de cadenas, una habilidad fundamental en el arsenal de un desarrollador. Hoy, nos sumergimos en un problema cautivador: identificar caracteres comunes en múltiples cadenas, y cómo abordamos su solución utilizando TypeScript.

El desafío desvelado

La tarea que se nos encomendó era aparentemente sencilla, pero engañosamente compleja: dada una matriz de cadenas, debíamos escribir una función que extrajera y devolviera una matriz de caracteres que aparecieran en la misma posición en todas las cadenas. Por ejemplo, dado el input ["abcd", "bcd", "cde", "cdef"], el output esperado sería ["c", "d"], lo que significa que 'c' y 'd' son los caracteres comunes compartidos entre todas las cadenas en las posiciones correspondientes.

Elaborando la solución

Nuestro viaje comenzó con la elección de TypeScript para la solución, una decisión impulsada por el robusto sistema de tipos de TypeScript, que mejora la fiabilidad del código y la productividad del desarrollador. El primer paso consistió en iterar sobre cada carácter de la primera cadena, utilizándolo como referencia para comparar con los caracteres correspondientes de las cadenas siguientes.

/**
 * Extrae y devuelve una matriz de caracteres que aparecen en la misma posición
 * en todas las cadenas dentro de la matriz de entrada.
 *
 * @param {string[]} words - Una matriz de cadenas que se van a analizar.
 * @returns {string[]} Una matriz de caracteres que son comunes en todas las cadenas proporcionadas,
 * manteniendo su orden de aparición en la primera cadena.
 */
export function extractCommonLetters(words: string[]): string[] {
  if (words.length === 0) {
    return []
  }

  const copiedWords = [...words]
  const result: string[] = []
  const referenceWord = copiedWords[0]

  // Itera sobre cada carácter de la primera palabra
  for (let i = 0; i < referenceWord.length; i++) {
    const currentChar = referenceWord[i]
    let isCharCommonAcrossWords = true

    // Comprueba si el carácter actual existe en cada una de las otras palabras
    for (let j = 1; j < copiedWords.length; j++) {
      const word = copiedWords[j]
      const charIndex = word.indexOf(currentChar)

      // Si el carácter no se encuentra, se interrumpe y se establece la bandera en falso
      if (charIndex === -1) {
        isCharCommonAcrossWords = false
        break
      } else {
        // Eliminar el carácter encontrado de la palabra para gestionar los duplicados
        copiedWords[j] = word.slice(0, charIndex) + word.slice(charIndex + 1)
      }
    }

    // Si el carácter es común en todas las palabras, se añade al resultado
    if (isCharCommonAcrossWords) {
      result.push(currentChar)
    }
  }

  return result
}

Este fragmento encapsula la esencia de nuestro enfoque, haciendo hincapié en la legibilidad y la lógica sencilla para abordar el problema.

Aventurándonos más allá: Probando la solución

Para validar nuestra solución, empleamos un conjunto de casos de prueba que cubrían varios escenarios, desde casos básicos hasta otros más complejos que implicaban caracteres especiales y sensibilidad a las mayúsculas y minúsculas. Estas pruebas exhaustivas aseguraron la robustez y la corrección de nuestro algoritmo en una amplia gama de entradas.

Analizando la complejidad espacial y temporal

Tras reflexionar, la complejidad temporal de nuestra solución está determinada principalmente por el número de caracteres de la primera cadena (denotaremos esto como N) y el número total de cadenas (denotaremos esto como M). Para cada carácter de la primera cadena, comprobamos su aparición en la posición correspondiente en todas las demás cadenas, lo que lleva a una complejidad temporal de O(N*M).

La complejidad espacial de nuestra solución es O(N), ya que almacenamos los caracteres comunes en una matriz. En el peor de los casos, cuando todos los caracteres son comunes en todas las cadenas, el tamaño de esta matriz sería proporcional a la longitud de la primera cadena.

Caminos hacia la mejora

Si bien nuestra solución es eficiente para un número moderado de cadenas y caracteres, siempre hay margen para la optimización. Aquí tienes algunas estrategias para mejorar aún más su rendimiento:

  1. Terminación anticipada: Si en algún momento un carácter no coincide en la posición correspondiente en todas las cadenas, podemos interrumpir el bucle de forma anticipada, ahorrando comparaciones innecesarias.

  2. Optimización para cadenas cortas: Empezar con la cadena más corta como referencia podría reducir el número de iteraciones, ya que minimiza el número máximo de caracteres que hay que comprobar.

  3. Procesamiento en paralelo: Para conjuntos de datos grandes, el uso de técnicas de procesamiento en paralelo para comparar caracteres entre cadenas de forma concurrente podría reducir significativamente el tiempo de ejecución.

  4. Técnicas de hashing: La utilización de un mapa hash para realizar un seguimiento de las posiciones y las apariciones de los caracteres podría ofrecer una forma más sofisticada de identificar caracteres comunes, especialmente cuando se trata de conjuntos extensos de cadenas.

Pensamientos finales

El desafío de los caracteres comunes sirve como un testimonio extraordinario de la elegancia de los problemas de manipulación de cadenas, invitando a los desarrolladores a profundizar en los matices de los algoritmos y las estructuras de datos. A través de TypeScript, no solo encontramos una solución, sino que también abrazamos un viaje de claridad, seguridad de tipos y resolución eficiente de problemas.

Al concluir, es esencial recordar que el viaje a través de los desafíos de codificación es tanto por el camino recorrido como por el destino alcanzado. Cada problema, incluido este, ofrece una oportunidad única para perfeccionar nuestras habilidades, repensar nuestros enfoques y, lo que es más importante, seguir aprendiendo.

Comentar en Twitter

COMPARTIR