XXVI Olimpíada Brasileira de Informática

Distância entre palavras

Vamos definir três tipos de operações básicas:

  • inserir uma letra em uma palavra;
  • remover uma letra de uma palavra;
  • substituir um letra de uma palavra.

Definimos também a distância entre duas palavras como o número mínimo de operações básicas para transformar a primeira palavra na segunda. Por exemplo, a distância entre as palavras maria e clara é 3:

  • remover a letra i: maria $ → $ mara
  • substituir a letra m pela letra c: mara $ → $ cara
  • inserir a letra l: cara $ → $ clara

    Questão 1. Qual a distância entre cansar e contar?
    1
    2
    3
    4
    5

    Questão 2. Qual a distância entre cabrito e aflito?
    1
    2
    3
    4
    5

    • Tarefas Iniciação Nível Júnior
    Promoção
    logo sbc
    Patrocínio
    Apoio
    Coordenação