Invertir Eficazmente el Orden de las Palabras en un Array de Caracteres

Invertir el orden de las palabras en un array de caracteres es un problema clásico que pone a prueba tu comprensión de algoritmos y manipulación de cadenas. Ya sea que te estés preparando para una entrevista o simplemente estés afinando tus habilidades de programación, dominar este desafío es bastante gratificante. En esta publicación, exploraremos el problema en detalle y desglosaremos una solución eficiente en C/C++.

El Problema

Dado un array de caracteres que forman una oración, nuestro objetivo es invertir el orden de las palabras sin alterar las letras individuales en las palabras. Por ejemplo, si introduces:

"esto es una cadena"

La salida debería ser:

'cadena una es esto'

El desafío especifica que esta operación debe lograrse en O(N) tiempo y O(1) espacio, lo que significa que no puedes usar funciones como split() o estructuras de datos como pilas que manipulan espacio adicional.

Análisis del Problema

Complejidad Temporal

El requisito de complejidad temporal O(N) significa que el algoritmo debe hacer un pase lineal a través de los datos. Por lo tanto, debemos evitar bucles anidados que aumenten la complejidad temporal.

Complejidad Espacial

Para cumplir con la complejidad espacial O(1), no podemos utilizar ninguna estructura de datos adicional para almacenamiento. Esto significa que las operaciones deben llevarse a cabo directamente dentro del array de entrada.

La Solución

Desglosemos la solución paso a paso. Utilizaremos un enfoque de dos pasadas para resolver este problema de manera eficiente.

Paso 1: Invertir Toda la Cadena

El primer paso es invertir todo el array. Esto transforma la cadena original en una cadena donde todos los caracteres están invertidos. Para nuestro ejemplo "esto es una cadena" después de la inversión:

"anadec anu se otse"

Paso 2: Invertir Cada Palabra

Ahora que hemos invertido la cadena completa, necesitamos invertir cada palabra individual para devolverlas al orden correcto. Aquí te mostramos cómo podemos implementar estos pasos en C/C++:

void swap(char* str, int i, int j) {
    char t = str[i];
    str[i] = str[j];
    str[j] = t;
}

void reverse_string(char* str, int length) {
    for(int i = 0; i < length / 2; i++) {
        swap(str, i, length - i - 1);
    }
}

void reverse_words(char* str) {
    int l = strlen(str);
    // Invertir toda la cadena
    reverse_string(str, strlen(str));
    int p = 0;

    // Encontrar los límites de las palabras e invertir palabra por palabra
    for(int i = 0; i < l; i++) {
        if(str[i] == ' ') {
            reverse_string(&str[p], i - p);  // Invertir la palabra identificada
            p = i + 1;
        }
    }
    // Finalmente, invertir la última palabra.
    reverse_string(&str[p], l - p);
}

Explicación del Código

1. Función Swap: Usamos una función auxiliar swap para intercambiar caracteres en el array.
2. Función Invertir Cadena: Esta función invierte los caracteres de la cadena utilizando la función swap.
3. Función Invertir Palabras: La función principal primero invierte todo el array de caracteres y luego itera a través de él para invertir las palabras individuales identificadas por espacios. La última palabra se maneja después de que termina el bucle.

Análisis de Complejidad

La inversión a través del array dos veces da como resultado una complejidad temporal O(N):

• Primer pase: O(N) para invertir toda la cadena.
• Segundo pase: O(N) para invertir cada palabra.

Por lo tanto, la complejidad temporal final se mantiene en O(N). La complejidad espacial es O(1) ya que no se utiliza espacio adicional aparte de las variables para la iteración.

Conclusión

Invertir el orden de las palabras en un array de caracteres de manera eficiente requiere una combinación de manipulaciones de cadenas y una comprensión del acceso indexado. El algoritmo presentado aquí demuestra un enfoque claro que cumple con los requisitos de O(N) tiempo y O(1) espacio mientras utiliza C/C++. Practica esta solución y descubrirás que es una excelente adición a tu conjunto de herramientas de programación.