Escreva uma função que recebe duas cadeias de caracteres e verifica se elas são iguais. Sua função deve devolver o valor -1 para indicar que a primeira cadeia é lexigraficamente menor que a segunda. O valor 1 deve ser devolvido quando a segunda cadeia é menor que a primeira. Quando as duas cadeias forem iguais, a função deve devolver zero.

Passo 1

O que o enunciado pede (em linguagem bem clara):
  • Escrever uma função que recebe duas cadeias de caracteres (vamos chamar de s_1 e s_2).
  • A função deve devolver:
    • -1 se s_1 for lexicograficamente menor que s_2.
    • 1 se s_1 for lexicograficamente maior que s_2.
    • 0 se s_1 e s_2 forem exatamente iguais.
Informações relevantes fornecidas (assunções usuais que vamos usar):
  • As entradas são duas strings (cadeias de caracteres). Vou tratar cada string como uma sequência de caracteres terminada por um caractere nulo quando fizer a implementação em C.
  • “Lexicograficamente” significa comparar caractere a caractere da esquerda para a direita; a primeira diferença determina a ordem. Se uma é prefixo estrito da outra, a mais curta é considerada menor.
  • Não foi pedida uma solução com regras de ordenação linguística ou Unicode avançada — aplicarei a comparação por códigos de caractere (por exemplo, por valores ASCII/Unicode code unit).

Passo 2

O que significa “comparar lexicograficamente” — explicação didática e intuitiva:
  • Imagine duas palavras numa lista de dicionário. Para saber qual vem primeiro, compara-se o primeiro caractere de cada palavra; se forem iguais, passa-se ao segundo, e assim por diante.
  • Formalizando: suponha que os caracteres nas posições i sejam c_1 = s_1[i] e c_2 = s_2[i]. Se c_1 < c_2 (pelo valor numérico do código do caractere), então s_1 < s_2. Se c_1 > c_2, então s_1 > s_2. Se todos os caracteres testados são iguais até que ambas terminem, então s_1 = s_2.
  • Exemplo rápido e concreto: s_1 = “casa” e s_2 = “caso”.
    • Comparando letra a letra: ‘c’ = ‘c’, ‘a’ = ‘a’, ‘s’ = ‘s’, mas no quarto caractere ‘a’ < ‘o’ (pelo código), então s_1 < s_2 e a função deve devolver -1.

Passo 3

Algoritmo passo a passo (o que você deve fazer na prova):
  1. Percorrer as duas strings ao mesmo tempo com um índice i começando em 0.
  2. Em cada passo, pegar c_1 = s_1[i] e c_2 = s_2[i].
  3. Se c_1 e c_2 forem diferentes:
    • Se c_1 < c_2 então retornar -1.
    • Caso contrário (isto é, c_1 > c_2) retornar 1.
  4. Se c_1 e c_2 forem iguais, incrementar i e repetir.
  5. Se chegar ao fim de ambas as strings ao mesmo tempo (ambos os caracteres são o terminador nulo), retornar 0.
  6. Se uma string terminar antes da outra (por exemplo, s_1 termina e s_2 continua), então a que terminou primeiro é menor; nesse caso retornar -1 se s_1 terminou antes, ou 1 se s_2 terminou antes.
Observações práticas importantes:
  • Em C usar comparação de valores de tipo unsigned char ao converter char para evitar problemas com caractere com bit de sinal.
  • Em linguagens de nível alto (Python, Java, etc.) a comparação de strings muitas vezes já tem suporte; mas no exame pode ser pedido que se implemente manualmente, então saber fazer caractere a caractere é essencial.

Passo 4

Complexidade e justificativa rápida (o que escrever numa prova para ganhar pontos):
  • Tempo: no pior caso é necessário comparar cada posição até o fim da string — isto é O(n), onde n é o comprimento da menor das duas strings.
  • Espaço: O(1) extra (apenas índice e variáveis temporárias).
  • Essas anotações mostram que a solução é eficiente.

Passo 5

Cuidados e casos de borda que aparecem em provas (e como tratá-los):
  • Strings vazias: se s_1 e/ou s_2 forem vazias, o algoritmo acima funciona — a string vazia é menor que qualquer string não vazia.
  • Sensibilidade a maiúsculas/minúsculas: ‘A’ e ‘a’ têm códigos diferentes; se o enunciado exigir comparação case-insensitive, é preciso normalizar (por exemplo convertendo para minúsculas) antes de comparar.
  • Unicode: comparar por code unit (por exemplo UTF-8 bytes ou UTF-16 code units) não é o mesmo que comparar por ordem linguística. Para a maioria dos exercícios básicos use comparação por unidades de código.
  • Em C, cuidado com ponteiros nulos (NULL) — em exercícios normalmente strings são válidas; se houver chance de NULL, cheque explicitamente.

Passo 6

Exemplos manuais (faça na prova para checar raciocínio):
  • Exemplo 1: s_1 = “abc”, s_2 = “abd”.
    • i=0: ‘a’=‘a’ → continua.
    • i=1: ‘b’=‘b’ → continua.
    • i=2: ‘c’ < ‘d’ → retorna -1.
  • Exemplo 2: s_1 = “teste”, s_2 = “tes”.
    • i=0,1,2: iguais; i=3: ‘t’ vs terminador nulo de s_2 s_2 terminou primeiro, então s_1 > s_2 → retorna 1.
  • Exemplo 3: s_1 = “”, s_2 = “” → retorna 0.

Passo 7

Como apresentar a solução na prova (comentário final)
  • Escreva em pseudocódigo o laço de comparação e as três condições de retorno ( -1, 1, 0); explique brevemente a complexidade e trate casos de borda (strings vazias, sensibilidade a maiúsculas).
  • Se pedirem código, implemente exatamente o que descreveu; siga as boas práticas da linguagem (por exemplo uso de unsigned char em C).

Resposta

/* Função em C que compara duas strings lexicograficamente.
   Retorna:
     -1 se s1 < s2
      0 se s1 == s2
      1 se s1 > s2
*/
#include <stddef.h>

int compare(const char *s1, const char *s2) {
    size_t i = 0;
    while (s1[i] != '\0' && s2[i] != '\0') {
        unsigned char c1 = (unsigned char) s1[i];
        unsigned char c2 = (unsigned char) s2[i];
        if (c1 < c2) return -1;
        if (c1 > c2) return 1;
        i++;
    }
    /* Se saímos do laço, pelo menos uma string terminou */
    if (s1[i] == '\0' && s2[i] == '\0') return 0;
    if (s1[i] == '\0') return -1;
    return 1;
}

Exercícios relacionados