Is Subsequence

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

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

Q: Qual é a relação entre Is Subsequence e a subsequência comum mais longa?

s é uma subsequência de t exatamente quando a subsequência comum mais longa entre elas tem comprimento n , que corresponde a todo s . A tabela de prefixos da primeira abordagem é a que você constrói para esse problema. Aqui, você só precisa saber se todo s se encaixa, então a passagem gulosa é suficiente.

FácilDois ponteiros

+10

Você recebe duas strings, s e t. Retorne true se você puder transformar t em s excluindo algumas de suas letras (possivelmente nenhuma), mantendo a ordem das letras restantes; caso contrário, retorne false. Por exemplo, ace é uma subsequência de abcde, mas aec não é.

Função

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

sstring: o texto a procurar
tstring: a string da qual excluir letras
Retornaboolean: verdadeiro se s puder 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: Remova b e d de abcde e resta ace, na mesma ordem.

Entrada: s = "aec"t = "abcde"
Saída: false
Explicação: t tem 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.

Para ir além

Se t permanecer fixo e você verificar um milhão de strings s em relação a ele, como prepararia t para que cada verificação seja mais rápida do que ler todo t?

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, o que sugere tentar várias posições de s. Você não precisa fazer isso: corresponder cada letra de s no primeiro lugar possível nunca é pior do que qualquer outra escolha, então uma única passagem da esquerda para a direita com dois ponteiros é suficiente para decidir.

Programação dinâmica sobre prefixos

Correta, mas não termina nos maiores testes

Intuição

Seja dp[i][j] indicando se as primeiras i letras de s cabem nas primeiras j letras de t. Elas cabem se já couberem sem t[j-1], ou se s[i-1] for igual a t[j-1] e as primeiras i-1 letras couberem em t[:j-1]. O prefixo vazio cabe em qualquer lugar, e a linha i lê apenas a linha i-1, então duas linhas de comprimento m+1 são suficientes.

A tabela preenche todas as células: com s de 25.000 letras e t de 50.000, isso resulta em 1.25 × 10^9 células.

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

Mantenha um ponteiro i para a próxima letra de s de que você precisa e pegue a primeira cópia dela que encontrar em t. Essa escolha é segura. Se um posicionamento válido usar uma cópia posterior de s[i], substituí-la pela cópia mais cedo mantém a ordem e deixa mais de t disponível para o restante de s. Portanto, se existir algum posicionamento, o algoritmo guloso o encontrará.

O loop lê cada letra de t no máximo uma vez e mantém dois índices: tempo O(n + m) e memória O(1).

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 tamanho 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

Pesquisar cada letra de s em qualquer lugar de t, em vez de depois da correspondência anterior. Isso aceita aec em abcde.
Usar a mesma ocorrência de uma letra duas vezes. noon não é uma subsequência de moon: seu único n, no índice 3, não pode ser a primeira e a última letra ao mesmo tempo.
Retornar se j chegou ao final de t. O loop geralmente termina ali, independentemente de s ter sido encontrado ou não; somente i informa isso.
Não parar quando t acabar. abc comparado com ab deve retornar false.
Ler s[i] depois que i chegou ao final de s. Em Python ou Java, essa leitura gera uma exceção, então verifique i antes de comparar.

Perguntas frequentes3

Qual é a complexidade de tempo de Is Subsequence?

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

Qual é a relação entre Is Subsequence e a subsequência comum mais longa?

s é uma subsequência de t exatamente quando a subsequência comum mais longa entre elas tem comprimento n, que corresponde a todo s. A tabela de prefixos da primeira abordagem é a que você constrói para esse problema. Aqui, você só precisa saber se todo s se encaixa, então a passagem gulosa é suficiente.

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.

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

Teste #1

Teste #2

Teste #3

Argumentos

s = "ace"
t = "abcde"

Saída Esperada

true