Inverter a ordem das palavras
A missão
Problema
Uma frase contém palavras separadas por um ou mais espaços, e também pode começar ou terminar com espaços. Retorne uma nova string com as palavras em ordem inversa, unidas por exatamente um espaço e sem espaços em nenhuma das pontas. Uma palavra é qualquer sequência de caracteres que não são espaços, e as letras dentro de uma palavra mantêm a sua ordem.
Exemplos
Input: s = " the sky is blue "
Output: "blue is sky the"
Por quê: os espaços extras somem e as palavras trocam de lugar
Input: s = "one"
Output: "one"
Por quê: uma única palavra não tem com quem trocar
Input: s = " "
Output: ""
Por quê: edge case: só espaços significa nenhuma palavra
Dicas
0 / 3
Inverter a string inteira também inverte as letras dentro de cada palavra, e não é isso que se pede. A unidade que se move é a palavra.
Se você ler a frase a partir da ponta direita, as palavras chegam exatamente na ordem de que a resposta precisa.
Comece no último caractere e percorra para a esquerda. Pule os espaços e então continue avançando até o próximo espaço para achar onde a palavra atual começa, e colete essa palavra. Repita até passar do início e então junte as palavras coletadas com espaços simples.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(n)
Restrições
- words are separated by one or more spaces
- leading and trailing spaces are possible
Solução
Varrer a partir da direita encontra a última palavra primeiro, então coletar as palavras na ordem em que aparecem já produz a frase invertida. Pular as sequências de espaços antes de cada palavra descarta o espaçamento extra, inclusive os espaços nas duas pontas. As letras de cada palavra são recortadas como um bloco, então nunca mudam de ordem. No Python do dia a dia, juntar o resultado invertido de split dá a mesma resposta em uma linha. O tempo é O(n) e o espaço é O(n) para a saída.
def reverse_words(s):
words, i = [], len(s) - 1
while i >= 0:
while i >= 0 and s[i] == " ":
i -= 1 # skip the gap before the next word
end = i
while i >= 0 and s[i] != " ":
i -= 1 # walk to the start of that word
if end > i:
words.append(s[i + 1:end + 1])
return " ".join(words)
print(reverse_words(" the sky is blue ")) # -> blue is sky the
print(reverse_words("one")) # -> one
print(reverse_words(" ")) # -> ""Travou na ideia, e não no código? Inverter as palavras explica isso.