Reverse a String

Q: Qual é a complexidade de tempo de inverter uma string?

Inverter leva tempo O(n) , porque cada caractere precisa ser movido para uma nova posição e cada um é processado uma vez. Criar uma nova string custa O(n) de espaço extra. Trocar os caracteres usando dois ponteiros exige apenas O(1) de espaço extra quando eles já estão em um array mutável.

Q: Como inverter uma string sem uma função de inversão integrada?

Copie os caracteres para um array, coloque um ponteiro em cada extremidade, troque os dois caracteres e mova os ponteiros um em direção ao outro até que se encontrem. Como alternativa, percorra do último índice até o primeiro e acrescente cada caractere a um construtor. Ambos produzem a string invertida em uma única passagem.

Q: Você consegue inverter uma string no próprio lugar?

Somente quando os caracteres estiverem em um buffer mutável, como um array de char em C, Java ou C#, uma lista em Python ou uma std::string em C++. Strings em Java, Python, JavaScript e muitas outras linguagens são imutáveis, então você as copia para um array, faz a troca dentro dele e cria uma nova string. A etapa de troca em si é feita no próprio local de qualquer maneira.

InicianteArrays e strings Dois ponteiros

+10

Você recebe uma string s composta por letras do alfabeto inglês e dígitos. Retorne uma nova string com os mesmos caracteres em ordem inversa, de modo que o último caractere venha primeiro e o primeiro venha por último. Mantenha cada caractere exatamente como está, incluindo maiúsculas e minúsculas.

Função

reverseString(s: string) → string

sstring: a string a ser invertida
Retornastring: os caracteres de s em ordem inversa

Restrições

1 ≤ s.length ≤ 10⁴
s contém apenas letras do alfabeto inglês (a a z, A a Z) e dígitos (0 a 9).

Exemplos

Entrada: s = "Coddy2026"
Saída: "6202yddoC"
Explicação: Leia Coddy2026 do último caractere ao primeiro: 6, 2, 0, 2, depois y, d, d, o e, por fim, o C maiúsculo.

Entrada: s = "noon"
Saída: "noon"
Explicação: noon é um palíndromo, então sua inversão é a mesma palavra. Os ns externos trocam de lugar, depois os dois os fazem o mesmo.

+14 testes ocultos ao enviar

Para ir além

Como você inverteria a ordem das palavras em uma frase, transformando hello big world em world big hello, enquanto cada palavra mantém suas letras na ordem original?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Cada caractere tem um destino fixo: o que está no índice i pertence ao índice n-1-i. Você pode escrever os caracteres em uma nova string nessa ordem ou trocá-los em pares, começando pelas duas extremidades. A troca é a versão que os entrevistadores pedem, porque o mesmo movimento com dois ponteiros inverte um array no próprio lugar e verifica se é um palíndromo.

Copie os caracteres do final

Intuição

O inverso de s começa com o último caractere de s, continua com o penúltimo e termina com o primeiro. Portanto, percorra um índice de n-1 até 0 e acrescente cada caractere à resposta à medida que o encontrar. Para Coddy2026, você acrescenta 6, 2, 0, 2, y e assim por diante, formando 6202yddoC.

Cada caractere é lido uma vez e escrito uma vez, então o trabalho é O(n). A resposta é uma segunda string de n caracteres, o que representa O(n) de espaço extra.

A forma como você acrescenta os caracteres importa. Adicionar um caractere a uma string imutável com + copia a string inteira a cada vez, e para n = 10^4 isso equivale a cerca de 5 × 10^7 cópias de caracteres. Reúna os caracteres em uma lista ou em um construtor de strings e junte-os uma única vez no final.

Algoritmo

Crie uma lista vazia ou um construtor de strings para a resposta.
Percorra i de n-1 até 0, em ordem decrescente.
Adicione s[i] à resposta.
Una os elementos da resposta em uma string e retorne-a.

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

Troque a partir das duas extremidades usando dois ponteiros

Intuição

Inverter troca os caracteres aos pares, de fora para dentro. O primeiro e o último trocam de lugar, depois o segundo e o penúltimo, e assim por diante em direção ao meio. Coloque um ponteiro left no índice 0 e um ponteiro right no índice n-1, troque os dois caracteres e mova ambos os ponteiros um passo para dentro.

Pare quando os ponteiros se encontrarem ou se cruzarem. Em noon, os ponteiros começam em 0 e 3, depois vão para 1 e 2 e, em seguida, se cruzam, após duas trocas. Em uma sequência de comprimento ímpar, como xYz, eles se encontram no caractere do meio, que já está em sua posição final e, portanto, nunca é tocado. Cada troca coloca dois caracteres em suas posições finais, então n / 2 trocas concluem a tarefa.

As trocas em si precisam de apenas uma variável temporária, espaço extra O(1). A maioria das linguagens não permite alterar uma string no próprio lugar, então primeiro você a copia para um array de caracteres, o que custa O(n). Em uma entrevista em que a entrada já é um array de caracteres, essa abordagem a inverte sem usar nenhuma memória extra.

Algoritmo

Copie s para um array de caracteres.
Defina left = 0 e right = n-1.
Enquanto left < right, troque os caracteres nas posições left e right, depois some 1 a left e subtraia 1 de right.
Transforme o array novamente em uma string e retorne-a.

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)

Armadilhas e casos extremos

Inverter parece exigir apenas uma linha, mas os erros se escondem nos limites do loop e na forma como a resposta é construída.

Fazer o loop percorrer left até n-1. Depois do meio, cada par é trocado uma segunda vez e a string volta a ficar como estava. Pare em left < right.
Começar o loop regressivo em n em vez de n-1, o que acessa uma posição além do final. Em Lua e R, os índices vão de 1 a n.
Construir a resposta com result = result + ch em uma string imutável. Cada etapa copia tudo o que foi acumulado até então, transformando uma tarefa linear em uma tarefa quadrática para entradas longas.
Esquecer o '\0' terminador em C. Um buffer de n bytes tem um byte a menos; aloque n + 1.
Trocar sem uma variável temporária: depois de chars[left] = chars[right], o caractere antigo da esquerda se perde, a menos que sua linguagem troque os dois valores de uma só vez.

Perguntas frequentes4

Qual é a complexidade de tempo de inverter uma string?

Inverter leva tempo O(n), porque cada caractere precisa ser movido para uma nova posição e cada um é processado uma vez. Criar uma nova string custa O(n) de espaço extra. Trocar os caracteres usando dois ponteiros exige apenas O(1) de espaço extra quando eles já estão em um array mutável.

Como inverter uma string sem uma função de inversão integrada?

Copie os caracteres para um array, coloque um ponteiro em cada extremidade, troque os dois caracteres e mova os ponteiros um em direção ao outro até que se encontrem. Como alternativa, percorra do último índice até o primeiro e acrescente cada caractere a um construtor. Ambos produzem a string invertida em uma única passagem.

Você consegue inverter uma string no próprio lugar?

Somente quando os caracteres estiverem em um buffer mutável, como um array de char em C, Java ou C#, uma lista em Python ou uma std::string em C++. Strings em Java, Python, JavaScript e muitas outras linguagens são imutáveis, então você as copia para um array, faz a troca dentro dele e cria uma nova string. A etapa de troca em si é feita no próprio local de qualquer maneira.

Por que o loop de dois ponteiros para no meio?

Cada troca coloca dois caracteres em suas posições finais, então, após n / 2 trocas, cada caractere está onde deveria estar. Continuar além do meio troca os mesmos pares novamente e desfaz o trabalho. Quando o comprimento é ímpar, o caractere do meio já está em seu próprio índice espelhado e não precisa ser trocado.

Python

def reverseString(s):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

s = "Coddy2026"

Esperado

"6202yddoC"