Valid Anagram

Q: Qual é a complexidade de tempo de Valid Anagram?

Contar as letras leva tempo O(n) e espaço extra O(1) , porque o array de contadores tem 26 entradas, independentemente do comprimento das strings. Ordenar as duas strings leva tempo O(n log n) e geralmente usa espaço O(n) para as cópias ordenadas.

Q: É melhor ordenar ou contar ao verificar se algo é um anagrama?

Em teoria, a contagem é mais rápida, O(n) contra O(n log n) , e pode parar assim que uma letra for usada em excesso. A ordenação é mais curta de escrever e funciona para qualquer alfabeto sem alterações. Em uma entrevista, mencione primeiro a ordenação e depois otimize para usar a contagem.

FácilHashing Ordenação

+10

Duas strings são anagramas quando uma é um rearranjo da outra: elas usam as mesmas letras, e cada letra aparece o mesmo número de vezes. Você recebe duas strings s e t formadas por letras minúsculas do alfabeto inglês. Retorne true se t for um anagrama de s, e false caso contrário.

Função

isAnagram(s: string, t: string) → boolean

sstring: a primeira string, letras minúsculas
tstring: a string para testar em relação a s
Retornaboolean: verdadeiro se t usa exatamente as letras de s, cada uma pelo mesmo número de vezes

Restrições

1 ≤ s.length, t.length ≤ 2 × 10⁴
s e t contêm apenas letras minúsculas do alfabeto inglês (a a z).
Os dois comprimentos podem ser diferentes.

Exemplos

Entrada: s = "listen"t = "silent"
Saída: true
Explicação: Ambas as palavras contêm um e, i, l, n, s e t, então silent é listen com as letras reorganizadas.

Entrada: s = "aabb"t = "abbb"
Saída: false
Explicação: Os comprimentos correspondem e ambos usam apenas a e b, mas aabb tem dois as e abbb tem um. As contagens precisam corresponder, não apenas as letras.

Entrada: s = "cat"t = "cast"
Saída: false
Explicação: cast tem quatro letras e cat tem três, então nenhuma reorganização de cat pode formar essa palavra.

+19 testes ocultos ao enviar

Para ir além

E se as strings pudessem conter qualquer caractere Unicode, em vez de a a z? Como você mudaria a contagem?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Um anagrama mantém a quantidade de cada letra e descarta a ordem. Portanto, você precisa de um resumo de cada string que esqueça onde as letras estavam, mas lembre quantas há de cada uma. A ordenação cria esse resumo em O(n log n); uma tabela com 26 contadores o cria em uma única passagem.

Ordene as duas strings

Intuição

Ordenar coloca as letras de uma string em ordem alfabética e apaga a posição inicial de cada uma. listen fica eilnst quando ordenada, assim como silent, então elas são anagramas. aabb continua aabb e abbb continua abbb; elas diferem no índice 1, então não são anagramas.

O teste funciona nos dois sentidos. Se t é uma reorganização de s, as duas contêm as mesmas letras com a mesma frequência, então a ordenação produz a mesma sequência. Se as sequências ordenadas são iguais, t usa exatamente as letras de s.

Compare primeiro os comprimentos: strings de comprimentos diferentes nunca são anagramas, e você pula as duas ordenações. Ordenar custa O(n log n) de tempo, e a maioria das linguagens ordena uma cópia dos caracteres, o que consome O(n) de espaço extra. Com n = 2 × 10^4, isso é rápido, mas a abordagem de contagem faz menos trabalho.

Algoritmo

Se os comprimentos de s e t forem diferentes, retorne false.
Copie os caracteres de cada string para um array.
Ordene os dois arrays.
Retorne true se os arrays ordenados forem iguais, elemento por elemento.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

Conte cada letra

Intuição

Como só podem aparecer 26 letras, mantenha um contador para cada letra em um array de 26 posições, com o índice 0 para a e o índice 25 para z. O índice de uma letra é o código do seu caractere menos o código de a. Percorra s e adicione 1 ao contador de cada letra; depois, percorra t e subtraia 1.

Você pode parar antes: um contador menor que 0 significa que t usou aquela letra mais vezes do que ela aparece em s. Para aabb e abbb, depois de percorrer s, os contadores são: a: 2 e b: 2. Então, t usa b três vezes; na terceira, o contador de b chega a -1, e você retorna false imediatamente.

Por que "nenhum contador ficou negativo" é suficiente? Os comprimentos são iguais, então a soma dos contadores é 0 após os dois percursos. Se nenhum for negativo, um contador positivo não teria com o que se equilibrar; portanto, todos os contadores são 0 e as contagens correspondem. É por isso que a verificação do comprimento é necessária, não apenas um atalho.

Cada string é lida uma vez, o que corresponde a O(n) de tempo. O array sempre contém 26 números, independentemente do comprimento, então o espaço extra é O(1).

Algoritmo

Se os comprimentos de s e t forem diferentes, retorne false.
Crie um array de 26 zeros.
Para cada letra de s, adicione 1 ao seu contador.
Para cada letra de t, subtraia 1 do seu contador; se ele ficar abaixo de 0, retorne false.
Retorne true.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for ch in t:
        index = ord(ch) - ord("a")
        counts[index] -= 1
        if counts[index] < 0:
            return False  # t uses this letter more often than s
    return True

Armadilhas e casos extremos

A maioria das respostas incorretas ocorre por verificar quais letras aparecem em vez de quantas vezes elas aparecem, ou por deixar de verificar o comprimento.

Comparar os conjuntos de letras. aabb e abbb usam exatamente a e b, mas não são anagramas.
Verificar se cada letra de t aparece em algum lugar de s sem riscá-la. aab e abb passam nesse teste nas duas direções.
Pular a verificação do comprimento na versão que conta as letras. Com s = ab e t = a, nenhum contador fica abaixo de 0, então o código retornaria true incorretamente.
Usar o código bruto do caractere como índice do array de contadores. a é 97, muito além do fim de um array de 26 posições; primeiro, subtraia o código de a. Em Lua e R, some 1, pois os arrays começam no índice 1.

Perguntas frequentes4

Qual é a complexidade de tempo de Valid Anagram?

Contar as letras leva tempo O(n) e espaço extra O(1), porque o array de contadores tem 26 entradas, independentemente do comprimento das strings. Ordenar as duas strings leva tempo O(n log n) e geralmente usa espaço O(n) para as cópias ordenadas.

É melhor ordenar ou contar ao verificar se algo é um anagrama?

Em teoria, a contagem é mais rápida, O(n) contra O(n log n), e pode parar assim que uma letra for usada em excesso. A ordenação é mais curta de escrever e funciona para qualquer alfabeto sem alterações. Em uma entrevista, mencione primeiro a ordenação e depois otimize para usar a contagem.

Como verificar anagramas que contêm caracteres Unicode?

Substitua o array de 26 contadores por um mapa hash de caracteres para contagens. Adicione 1 para cada caractere de s, subtraia 1 para cada caractere de t e verifique se todas as contagens terminam em 0. Leia as strings como caracteres inteiros, não como bytes, para que um caractere armazenado em vários bytes seja contado uma única vez.

Por que usar um único array de contadores em vez de dois?

Duas matrizes, uma para cada string, também funcionam: conte cada string e depois compare as matrizes. Uma única matriz que aumenta para s e diminui para t usa metade da memória e permite retornar false assim que um contador fica negativo, sem precisar de um loop final de comparação.

Python

def isAnagram(s, t):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

s = "listen"
t = "silent"

Esperado

true