Reverse Words in a String

Q: Qual é a complexidade de tempo de Inverter palavras em uma string?

As duas abordagens têm tempo de execução O(n) para uma string de comprimento n , porque cada caractere é lido e escrito um número constante de vezes. A divisão usa O(n) de espaço extra para a lista de palavras. Inverter a string inteira e, em seguida, cada palavra requer O(1) de espaço extra em um array de caracteres que você pode editar.

MédioArrays e strings Dois ponteiros

+10

Você recebe uma string s composta por palavras e espaços. Uma palavra é uma sequência de letras e dígitos sem espaços dentro dela. As palavras podem ser separadas por mais de um espaço, e s pode começar ou terminar com espaços.

Retorne as palavras na ordem inversa, unidas por exatamente um espaço, sem espaço no início nem no fim. Cada palavra mantém sua grafia; somente a ordem das palavras muda.

Função

reverseWords(s: string) → string

sstring: letras, dígitos e espaços contendo pelo menos uma palavra
Retornastring: as palavras de s em ordem inversa, separadas por espaços simples

Restrições

1 ≤ s.length ≤ 10⁴
s contém apenas letras do alfabeto inglês, dígitos e espaços.
s contém pelo menos uma palavra.

Exemplos

Entrada: s = "Coddy runs in 15 languages"
Saída: "languages 15 in runs Coddy"
Explicação: As palavras são Coddy, runs, in, 15 e languages. Lidas da última para a primeira, elas formam languages 15 in runs Coddy; 15 conta como uma palavra porque palavras podem conter dígitos.

Entrada: s = " practice makes progress "
Saída: "progress makes practice"
Explicação: Os espaços nas duas extremidades são removidos, e as sequências de dois e três espaços entre as palavras são reduzidas a um. As três palavras saem da última para a primeira: progress makes practice.

Entrada: s = " single "
Saída: "single"
Explicação: Uma lista com uma palavra é lida da mesma forma ao contrário. Apenas os espaços ao redor dela desaparecem, então a resposta é single.

Para ir além

Você consegue inverter as palavras, mas manter os espaços de s: as mesmas sequências de espaços, com os mesmos comprimentos, na mesma ordem?

Solução

A ordem das palavras é uma inversão; os espaços são onde as soluções falham. Os espaços no início ou no fim e os espaços repetidos entre as palavras devem desaparecer, deixando exatamente um espaço entre as palavras na resposta. Você pode dividir em uma lista de palavras ou inverter a string inteira e, em seguida, cada palavra dentro de um array.

Divida em palavras e junte-as na ordem inversa

Intuição

Divida s em suas palavras, inverta a lista e una-a com espaços simples. A divisão exige cuidado: dividir " practice makes progress " em cada espaço resulta em seis partes vazias ao redor das três palavras. Remova as partes vazias e a lista será practice, makes, progress.

A divisão lê cada caractere uma vez e a junção escreve cada caractere mantido uma vez, então o tempo é O(n) para uma string de comprimento n. A lista de palavras e a resposta ocupam O(n) de espaço extra.

Algoritmo

Divida s nos espaços.
Descarte os elementos vazios.
Inverta a lista de palavras.
Junte as palavras com um espaço entre cada uma e retorne o resultado.

def reverseWords(s):
    # split() with no argument treats any run of spaces as one separator
    # and ignores spaces at both ends.
    words = s.split()
    words.reverse()
    return " ".join(words)

Inverta a string inteira e, depois, cada palavra

Intuição

Inverter a string inteira coloca as palavras na ordem certa, mas escreve cada uma ao contrário: Coddy runs in 15 languages se torna segaugnal 51 ni snur yddoC. Inverter cada palavra separadamente resulta então em languages 15 in runs Coddy.

Os espaços são tratados na mesma passagem. Um índice read percorre o array invertido e ignora os espaços; um índice write marca onde vai o próximo caractere mantido. A cópia nunca sobrescreve um caractere de que você ainda precisa, porque write nunca ultrapassa read: o espaço escrito antes de uma palavra ocupa o lugar de pelo menos um espaço que read ignorou.

Cada caractere é copiado no máximo uma vez e trocado no máximo duas vezes, então o tempo é O(n), com O(1) de espaço extra em um buffer de caracteres que você pode editar. Aqui, as strings chegam como valores, então cada solução cria uma cópia de trabalho de s: O(n) de memória no total.

Algoritmo

Copie s em um array de caracteres e inverta o array inteiro.
Percorra o array com um índice de leitura e ignore os espaços.
Em cada palavra, escreva primeiro um espaço, a menos que seja a primeira palavra; em seguida, copie os caracteres da palavra para o índice de escrita.
Inverta o trecho que você copiou para que a palavra fique na ordem correta.
Retorne os primeiros write caracteres.

def reverseWords(s):
    chars = list(s)

    def reverse(lo, hi):
        while lo < hi:
            chars[lo], chars[hi] = chars[hi], chars[lo]
            lo += 1
            hi -= 1

    n = len(chars)
    reverse(0, n - 1)  # words in the right order, each spelled backwards
    write = 0
    read = 0
    while read < n:
        if chars[read] == " ":
            read += 1
            continue
        if write > 0:
            chars[write] = " "  # one space before every word but the first
            write += 1
        start = write
        while read < n and chars[read] != " ":
            chars[write] = chars[read]
            write += 1
            read += 1
        reverse(start, write - 1)  # spell the word forwards again
    return "".join(chars[:write])

Armadilhas e casos extremos

Dividir usando um único espaço e manter cada parte. "a b" é dividido em a, uma parte vazia e b, e a junção coloca dois espaços de volta: "b a".
Confiar que a divisão descarte as extremidades. O split(" ") do Java descarta as partes vazias no final, mas as mantém no início, então " a b" ainda deixa uma.
Adicionar um espaço após cada palavra, incluindo a última, fazendo com que a resposta termine com um espaço. Coloque o espaço antes de cada palavra, exceto a primeira.
Fazer apenas uma inversão na versão in-place. Inverter apenas as palavras resulta em yddoC snur ni 51 segaugnal.
Em PHP e R, uma entrada composta apenas por dígitos, como 2026, pode chegar como um número. Converta-a em uma string antes de dividi-la.

Perguntas frequentes3

Qual é a complexidade de tempo de Inverter palavras em uma string?

As duas abordagens têm tempo de execução O(n) para uma string de comprimento n, porque cada caractere é lido e escrito um número constante de vezes. A divisão usa O(n) de espaço extra para a lista de palavras. Inverter a string inteira e, em seguida, cada palavra requer O(1) de espaço extra em um array de caracteres que você pode editar.

Como você lida com vários espaços entre as palavras?

Considere uma palavra como uma sequência de caracteres que não sejam espaços e nunca copie espaços da entrada. Uma divisão sem separador em Python e Ruby, strings.Fields em Go e split_whitespace em Rust já ignoram cada sequência de espaços e ambas as extremidades; em outros lugares, descarte as partes vazias. Em seguida, escreva um espaço entre as palavras.

Você consegue inverter as palavras sem uma função split?

Sim. Percorra a partir da extremidade direita: ignore os espaços, marque onde uma palavra termina, mova-se para a esquerda até o início dela e acrescente a palavra com um espaço antes, a menos que seja a primeira. Cada caractere é visitado uma vez, então o tempo permanece O(n), e as palavras aparecem na ordem inversa sem precisar inverter uma lista.

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

Teste #1

Teste #2

Teste #3

Argumento

s = "Coddy runs in 15 languages"

Saída Esperada

"languages 15 in runs Coddy"