Reverse a String

Q: ¿Cuál es la complejidad temporal de invertir una cadena?

Invertir requiere un tiempo de O(n) , porque cada carácter debe moverse a una nueva posición y se procesa una sola vez. Crear una cadena nueva cuesta O(n) de espacio adicional. Intercambiar con dos punteros requiere solo O(1) de espacio adicional cuando los caracteres ya están en un arreglo mutable.

Q: ¿Cómo inviertes una cadena sin una función de inversión incorporada?

Copia los caracteres en un arreglo, coloca un puntero en cada extremo, intercambia los dos caracteres y mueve los punteros uno hacia el otro hasta que se encuentren. Como alternativa, recorre desde el último índice hasta el primero y agrega cada carácter a un generador. Ambos métodos producen la cadena invertida en una sola pasada.

Q: ¿Puedes invertir una cadena en el mismo lugar?

Solo cuando los caracteres se encuentran en un búfer mutable, como un arreglo de char en C, Java o C#, una lista en Python o un std::string en C++. Las cadenas en Java, Python, JavaScript y muchos otros lenguajes son inmutables, así que las copias en un arreglo, intercambias los elementos dentro de él y construyes una cadena nueva. El paso de intercambio en sí se realiza in situ en ambos casos.

PrincipianteArrays y cadenas Dos punteros

+10

Recibes una cadena s formada por letras inglesas y dígitos. Devuelve una nueva cadena con los mismos caracteres en orden inverso, de modo que el último carácter aparezca primero y el primero al final. Conserva cada carácter exactamente como está, incluida su mayúscula o minúscula.

Función

reverseString(s: string) → string

sstring: la cadena que se va a invertir
Devuelvestring: los caracteres de s en orden inverso

Restricciones

1 ≤ s.length ≤ 10⁴
s contiene solo letras inglesas (a a z, A a Z) y dígitos (0 a 9).

Ejemplos

Entrada: s = "Coddy2026"
Salida: "6202yddoC"
Explicación: Lee Coddy2026 desde su último carácter hasta el primero: 6, 2, 0, 2, después y, d, d, o y, por último, la C mayúscula.

Entrada: s = "noon"
Salida: "noon"
Explicación: noon es un palíndromo, así que al invertirlo se obtiene la misma palabra. Las n exteriores intercambian posiciones y después lo hacen las dos o.

+14 pruebas ocultas al enviar

Para ir más allá

¿Cómo invertirías el orden de las palabras de una oración, convirtiendo hello big world en world big hello, mientras cada palabra mantiene sus letras en orden?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Cada carácter tiene un destino fijo: el que está en el índice i va en el índice n-1-i. Puedes escribir los caracteres en una nueva cadena en ese orden o intercambiarlos por pares desde ambos extremos. El intercambio es la versión que suelen pedir en las entrevistas, porque el mismo movimiento de dos punteros invierte un arreglo en el sitio y comprueba si es un palíndromo.

Cuenta los caracteres desde el final

Intuición

El reverso de s empieza con el último carácter de s, continúa con el penúltimo y termina con el primero. Así que recorre un índice desde n-1 hasta 0 y añade cada carácter a la respuesta a medida que lo encuentres. Para Coddy2026 añades 6, 2, 0, 2, y y así sucesivamente, lo que da como resultado 6202yddoC.

Cada carácter se lee una vez y se escribe una vez, así que el trabajo es O(n). La respuesta es una segunda cadena de n caracteres, lo que requiere O(n) espacio adicional.

La forma de añadir importa. Añadir un carácter a una cadena inmutable con + copia toda la cadena cada vez, y para n = 10^4 eso supone unas 5 × 10^7 copias de caracteres. Recopila los caracteres en una lista o en un generador de cadenas y únelos una sola vez al final.

Algoritmo

Crea una lista vacía o un constructor de cadenas para la respuesta.
Recorre i desde n-1 hasta 0.
Añade s[i] a la respuesta.
Une los elementos de la respuesta en una cadena y devuélvela.

def reverseString(s):
    result = []
    for i in range(len(s) - 1, -1, -1):
        result.append(s[i])
    return "".join(result)

Cambia desde ambos extremos con dos punteros

Intuición

Invertir intercambia los caracteres por pares desde los extremos hacia el centro. El primero y el último intercambian posiciones, después lo hacen el segundo y el penúltimo, y así sucesivamente hacia el centro. Coloca un puntero left en el índice 0 y un puntero right en el índice n-1, intercambia los dos caracteres y mueve ambos punteros un paso hacia el centro.

Detente cuando los punteros se encuentren o se crucen. En noon, los punteros empiezan en 0 y 3, después avanzan a 1 y 2, y luego se cruzan, tras dos intercambios. Si la longitud es impar, como en xYz, se encuentran en el carácter central, que ya está en su posición final, así que nunca se toca. Cada intercambio coloca dos caracteres en sus posiciones finales, por lo que n / 2 intercambios bastan para terminar.

Los intercambios en sí solo necesitan una variable temporal, es decir, espacio adicional O(1). La mayoría de los lenguajes no permiten modificar una cadena in situ, así que primero la copias en un arreglo de caracteres, lo que cuesta O(n). En una entrevista en la que la entrada ya es un arreglo de caracteres, este enfoque la invierte sin usar memoria adicional.

Algoritmo

Copia s en un arreglo de caracteres.
Establece left = 0 y right = n-1.
Mientras left < right, intercambia los caracteres en left y right, después suma 1 a left y resta 1 a right.
Convierte el arreglo de nuevo en una cadena y devuélvela.

def reverseString(s):
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return "".join(chars)

Errores comunes y casos límite

Revertir parece una sola línea, pero los errores se esconden en los límites de los bucles y en cómo se construye el resultado.

Recorrer left hasta n-1. Después de la mitad, cada par se intercambia una segunda vez y la cadena queda igual que al principio. Detente en left < right.
Iniciar el bucle hacia atrás en n en lugar de n-1, lo que lee una posición más allá del final. En Lua y R, los índices van de 1 a n.
Construir el resultado con result = result + ch en una cadena inmutable. Cada paso copia todo lo acumulado hasta ese momento, lo que convierte una tarea lineal en una cuadrática con entradas largas.
Olvidar el '\0' de terminación en C. Un búfer de n bytes se queda corto; asigna n + 1.
Intercambiar sin una variable temporal: después de chars[left] = chars[right], el carácter anterior de la izquierda desaparece, a menos que tu lenguaje intercambie ambos valores a la vez.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de invertir una cadena?

Invertir requiere un tiempo de O(n), porque cada carácter debe moverse a una nueva posición y se procesa una sola vez. Crear una cadena nueva cuesta O(n) de espacio adicional. Intercambiar con dos punteros requiere solo O(1) de espacio adicional cuando los caracteres ya están en un arreglo mutable.

¿Cómo inviertes una cadena sin una función de inversión incorporada?

Copia los caracteres en un arreglo, coloca un puntero en cada extremo, intercambia los dos caracteres y mueve los punteros uno hacia el otro hasta que se encuentren. Como alternativa, recorre desde el último índice hasta el primero y agrega cada carácter a un generador. Ambos métodos producen la cadena invertida en una sola pasada.

¿Puedes invertir una cadena en el mismo lugar?

Solo cuando los caracteres se encuentran en un búfer mutable, como un arreglo de char en C, Java o C#, una lista en Python o un std::string en C++. Las cadenas en Java, Python, JavaScript y muchos otros lenguajes son inmutables, así que las copias en un arreglo, intercambias los elementos dentro de él y construyes una cadena nueva. El paso de intercambio en sí se realiza in situ en ambos casos.

¿Por qué el bucle de dos punteros se detiene en el medio?

Cada intercambio coloca dos caracteres en sus posiciones finales, así que después de n / 2 intercambios cada carácter está donde le corresponde. Continuar más allá de la mitad vuelve a intercambiar los mismos pares y deshace el trabajo. Cuando la longitud es impar, el carácter del medio ya está en su propio índice reflejado y no necesita ningún intercambio.

Python

def reverseString(s):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

s = "Coddy2026"

Esperado

"6202yddoC"