Inverter Eficientemente a Ordem das Palavras em um Array de Caracteres

Inverter a ordem das palavras em um array de caracteres é um problema clássico que testa sua compreensão de algoritmos e manipulação de strings. Se você está se preparando para uma entrevista ou apenas aperfeiçoando suas habilidades de programação, dominar esse desafio é bastante recompensador. Neste post, exploraremos o problema em detalhes e descreveremos uma solução eficiente em C/C++.

O Problema

Dado um array de caracteres formando uma frase, nosso objetivo é inverter a ordem das palavras sem alterar as letras individuais nas palavras. Por exemplo, se você inserir:

"isto é uma string"

A saída deve ser:

'string uma é isto'

O desafio especifica que essa operação deve ser realizada em tempo O(N) e espaço O(1), o que significa que você não pode usar funções como split() ou quaisquer estruturas de dados como pilhas que manipulem espaço extra.

Analisando o Problema

Complexidade de Tempo

A exigência de complexidade de tempo O(N) significa que o algoritmo deve fazer uma passagem linear pelos dados. Assim, devemos evitar loops aninhados que aumentam a complexidade de tempo.

Complexidade de Espaço

Para complexidade de espaço O(1), não podemos usar nenhuma estrutura de dados adicional para armazenamento. Isso significa que as operações devem ocorrer diretamente no array de entrada.

A Solução

Vamos dividir a solução passo a passo. Utilizaremos uma abordagem de duas passagens para resolver esse problema de forma eficiente.

Passo 1: Inverter a String Inteira

O primeiro passo é inverter todo o array. Isso transforma a string original em uma string onde todos os caracteres estão invertidos. Para nosso exemplo "isto é uma string" após a inversão:

"gnirts uma é otsi"

Passo 2: Inverter Cada Palavra

Agora que temos a string inteira invertida, precisamos inverter cada palavra individual para colocá-las de volta na ordem correta. Veja como podemos implementar esses passos em 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);
    // Inverter toda a string
    reverse_string(str, strlen(str));
    int p = 0;
 
    // Encontrar os limites das palavras e inverter palavra por palavra
    for(int i = 0; i < l; i++) {
        if(str[i] == ' ') {
            reverse_string(&str[p], i - p);  // Inverter a palavra identificada
            p = i + 1;
        }
    }
    // Finalmente inverter a última palavra.
    reverse_string(&str[p], l - p);
}

Explicação do Código

1. Função Swap: Usamos uma função auxiliar swap para fazer a troca de caracteres no array.
2. Função Inverter String: Esta função inverte os caracteres da string utilizando a função swap.
3. Função Inverter Palavras: A função principal primeiro inverte todo o array de caracteres e depois itera por ele para inverter palavras individuais identificadas por espaços. A última palavra é tratada após o fim do loop.

Análise de Complexidade

O processo de inverter o array duas vezes gera a complexidade de tempo O(N):

• Primeira passagem: O(N) para inverter toda a string.
• Segunda passagem: O(N) para inverter cada palavra.

Assim, a complexidade de tempo final permanece O(N). A complexidade de espaço é O(1), uma vez que nenhum espaço extra é utilizado além de variáveis para iteração.

Conclusão

Inverter a ordem das palavras em um array de caracteres eficientemente requer uma combinação de manipulações de strings e uma compreensão do acesso indexado. O algoritmo apresentado aqui demonstra uma abordagem clara que atende aos requisitos de tempo O(N) e espaço O(1) enquanto usa C/C++. Pratique essa solução e você encontrará uma excelente adição ao seu arsenal de programação!