Is Subsequence

Q: Qual é a complexidade de tempo de Is Subsequence?

A solução com dois ponteiros é executada em O(n + m) de tempo, em que n e m são os comprimentos de s e t , e usa O(1) de memória extra. Na prática, o loop para após no máximo m etapas. A tabela de prefixos leva O(n × m) de tempo.

Q: Por que a abordagem gulosa de dois ponteiros funciona para Is Subsequence?

Combinar uma letra de s na posição mais cedo possível em t deixa o maior trecho possível restante de t para as letras restantes. Qualquer posicionamento que use uma ocorrência posterior pode ser alterado para usar a anterior sem quebrar a ordem; portanto, se existir algum posicionamento, o algoritmo guloso o encontra.

Q: Como testar rapidamente várias strings contra o mesmo t?

Prepare t uma vez: para cada letra, armazene a lista ordenada dos índices em que ela aparece. Para posicionar s[i] , faça uma busca binária na lista dessa letra pelo primeiro índice após a correspondência anterior. Cada verificação passa a custar O(n log m) em vez de O(m) .

FácilDois ponteiros

+10

Você recebe duas strings, s e t. Retorne true se você puder transformar t em s removendo algumas de suas letras (possivelmente nenhuma) enquanto as letras restantes mantêm sua ordem, e false caso contrário. Por exemplo, ace é uma subsequência de abcde, mas aec não é.

Função

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

sstring: o texto a ser procurado
tstring: o texto do qual excluir letras
Retornaboolean: verdadeiro se s pode ser lido dentro de t em ordem, possivelmente com lacunas

Restrições

1 ≤ s.length ≤ 3 × 10⁴
1 ≤ t.length ≤ 5 × 10⁴
s e t contêm apenas letras minúsculas do alfabeto inglês.

Exemplos

Entrada: s = "ace"t = "abcde"
Saída: true
Explicação: Exclua b e d de abcde, e ace sobra, na mesma ordem.

Entrada: s = "aec"t = "abcde"
Saída: false
Explicação: t tem todas as três letras, mas o único c fica antes do único e. Depois que você usa o e no índice 4, não resta nenhum c à sua direita.

Entrada: s = "moon"t = "monsoon"
Saída: true
Explicação: Use o m no índice 0, os os nos índices 1 e 4, e o n no índice 6 de monsoon. As letras entre eles são excluídas.

+20 testes ocultos ao enviar

Para ir além

Suponha que t permaneça igual e que você precise verificar um milhão de strings diferentes s em relação a ele. Como você prepararia t para que cada verificação fosse mais rápida do que ler t inteiro novamente?

Dicas

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

0 de 3 abertas

Solução

Uma subsequência pode pular letras de t em qualquer lugar, então pode parecer que você precisa tentar várias maneiras de colocar s dentro de t. Não precisa. Correspondendo cada letra de s à primeira posição possível, o resultado nunca será pior do que com qualquer outra escolha, e isso transforma a busca em uma única passagem da esquerda para a direita com dois ponteiros.

Programação dinâmica sobre prefixos

Correta, mas não termina nos maiores testes

Intuição

Faça uma pergunta menor: as primeiras i letras de s cabem nas primeiras j letras de t? Chame a resposta de dp[i][j]. Se elas couberem em t[:j-1], também cabem em t[:j], já que você pode remover t[j-1]. Se s[i-1] for igual a t[j-1], você também pode usar essa letra; nesse caso, as primeiras i-1 letras de s precisam caber em t[:j-1]. Então, dp[i][j] = dp[i][j-1] or (s[i-1] == t[j-1] and dp[i-1][j-1]), e o prefixo vazio de s cabe em qualquer lugar.

A linha i só lê a linha i-1, então duas linhas de comprimento m+1 são suficientes. A resposta é a última célula da última linha.

Esta é a mesma tabela que você monta para a subsequência comum mais longa, e está correta, mas preenche todas as células. Com s de 25.000 letras e t de 50.000, isso representa 1.25 × 10^9 células, muito mais do que uma única passagem pelas duas strings exige.

Algoritmo

Crie uma linha prev com m+1 valores, todos true: um s vazio se encaixa em todo prefixo de t.
Para cada i de 1 a n, crie uma linha cur com cur[0] = false.
Para cada j de 1 a m, defina cur[j] como cur[j-1] ou como prev[j-1] quando s[i-1] for igual a t[j-1].
Substitua prev por cur.
Retorne prev[m].

def isSubsequence(s, t):
    n, m = len(s), len(t)
    # prev[j]: the first i-1 letters of s fit inside t[:j]. An empty s fits anywhere.
    prev = [True] * (m + 1)
    for i in range(1, n + 1):
        cur = [False] * (m + 1)
        for j in range(1, m + 1):
            cur[j] = cur[j - 1] or (s[i - 1] == t[j - 1] and prev[j - 1])
        prev = cur
    return prev[m]

Dois ponteiros com correspondência gulosa

Intuição

Percorra t da esquerda para a direita e mantenha um ponteiro i para a próxima letra de s que ainda precisa ser encontrada. Quando t[j] for igual a s[i], use essa letra e avance i. De qualquer forma, avance j. Se i chegar ao fim de s, todas as letras encontraram um lugar na ordem correta.

Por que é seguro escolher a primeira correspondência? Suponha que alguma disposição válida use uma cópia posterior de s[i]. Trocá-la pela cópia mais cedo mantém a ordem e deixa mais elementos de t à direita para o restante de s, então a escolha gulosa nunca descarta uma disposição existente. Para moon em monsoon, o ponteiro pega o o no índice 1, pula n e s, pega o o no índice 4 e termina no n no índice 6.

j visita cada letra de t uma vez e i só avança, então o loop é executado no máximo m vezes. Dois índices são tudo de que ele precisa em termos de memória.

Algoritmo

Defina i = 0 para s e j = 0 para t.
Enquanto ambos os índices estiverem dentro de suas strings, compare s[i] com t[j].
Se forem iguais, incremente i.
Incremente j em todos os casos.
Retorne se i é igual ao comprimento de s.

def isSubsequence(s, t):
    i = j = 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == len(s)

Armadilhas e casos extremos

O loop de dois ponteiros é curto, e seus bugs ficam nas extremidades.

Procurar cada letra de s em qualquer lugar de t, em vez de depois da correspondência anterior. Isso aceita aec em abcde, onde a ordem está incorreta.
Usar a mesma ocorrência de uma letra duas vezes. noon não é uma subsequência de moon: moon tem apenas um n, no índice 3, e ele não pode ser ao mesmo tempo a primeira e a última letra de noon.
Retornar se j chegou ao fim de t. O loop geralmente termina ali, independentemente de s ter sido encontrado ou não; só i informa isso.
Esquecer que s pode ser mais longo que t. abc em relação a ab deve retornar false, o que o loop faz desde que pare quando t acabar.
Ler s[i] depois que i chegou ao fim de s. Em Python ou Java, essa leitura gera uma exceção, então verifique i antes de comparar.

Perguntas frequentes4

Qual é a complexidade de tempo de Is Subsequence?

A solução com dois ponteiros é executada em O(n + m) de tempo, em que n e m são os comprimentos de s e t, e usa O(1) de memória extra. Na prática, o loop para após no máximo m etapas. A tabela de prefixos leva O(n × m) de tempo.

Por que a abordagem gulosa de dois ponteiros funciona para Is Subsequence?

Combinar uma letra de s na posição mais cedo possível em t deixa o maior trecho possível restante de t para as letras restantes. Qualquer posicionamento que use uma ocorrência posterior pode ser alterado para usar a anterior sem quebrar a ordem; portanto, se existir algum posicionamento, o algoritmo guloso o encontra.

Como testar rapidamente várias strings contra o mesmo t?

Prepare t uma vez: para cada letra, armazene a lista ordenada dos índices em que ela aparece. Para posicionar s[i], faça uma busca binária na lista dessa letra pelo primeiro índice após a correspondência anterior. Cada verificação passa a custar O(n log m) em vez de O(m).

Qual é a diferença entre uma subsequência e uma substring?

Uma substring é um bloco de letras consecutivas, enquanto uma subsequência pode pular letras, desde que a ordem permaneça a mesma. ace é uma subsequência de abcde, mas não é uma substring dele. Toda substring é uma subsequência, mas o contrário não é verdade.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

s = "ace"
t = "abcde"

Esperado

true