Is Subsequence

Q: Quelle est la complexité temporelle de Is Subsequence ?

La solution à deux pointeurs s’exécute en O(n + m) temps, où n et m sont les longueurs de s et t , avec une mémoire supplémentaire de O(1) . La boucle s’arrête après au plus m étapes. La table des préfixes nécessite un temps de O(n × m) .

Q: Quel est le lien entre Is Subsequence et la plus longue sous-séquence commune ?

s est une sous-séquence de t exactement lorsque leur plus longue sous-séquence commune a une longueur de n , soit la longueur totale de s . Le tableau des préfixes de la première approche est celui que tu construis pour ce problème. Ici, tu as seulement besoin de savoir si tout s tient, donc un parcours glouton suffit.

FacileDeux pointeurs

+10

On vous donne deux chaînes, s et t. Renvoyez true si vous pouvez transformer t en s en supprimant certaines de ses lettres (éventuellement aucune), tout en conservant l’ordre des lettres restantes, et false sinon. Par exemple, ace est une sous-séquence de abcde, mais aec n’en est pas une.

Fonction

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

sstring: la chaîne à rechercher
tstring: la chaîne dont supprimer des lettres
Renvoieboolean: vrai si s peut être lu dans t dans l’ordre, éventuellement avec des espaces

Contraintes

1 ≤ s.length ≤ 3 × 10⁴
1 ≤ t.length ≤ 5 × 10⁴
s et t ne contiennent que des lettres minuscules anglaises.

Exemples

Entrée: s = "ace"t = "abcde"
Sortie: true
Explication: Supprimez b et d de abcde et il reste ace, dans le même ordre.

Entrée: s = "aec"t = "abcde"
Sortie: false
Explication: t comporte les trois lettres, mais le seul c se trouve avant le seul e. Après avoir utilisé le e à l’index 4, il ne reste aucun c à sa droite.

Entrée: s = "moon"t = "monsoon"
Sortie: true
Explication: Utilisez le m à l’index 0, les o aux index 1 et 4, et le n à l’index 6 de monsoon. Les lettres situées entre ces lettres sont supprimées.

Pour aller plus loin

Si t reste fixe et que tu vérifies un million de chaînes s par rapport à lui, comment préparerais-tu t pour que chaque vérification soit plus rapide que de parcourir tout t ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Une sous-séquence peut omettre des lettres de t n’importe où, ce qui suggère d’essayer de nombreux emplacements de s. Ce n’est pas nécessaire : faire correspondre chaque lettre de s à la première position possible n’est jamais moins avantageux qu’un autre choix ; un seul parcours de gauche à droite avec deux pointeurs suffit donc à le déterminer.

Programmation dynamique sur les préfixes

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Soit dp[i][j] qui indique si les i premières lettres de s tiennent dans les j premières lettres de t. Elles tiennent si elles tenaient déjà sans t[j-1], ou si s[i-1] est égal à t[j-1] et que les i-1 premières lettres tiennent dans t[:j-1]. Le préfixe vide tient partout, et la ligne i ne lit que la ligne i-1, donc deux lignes de longueur m+1 suffisent.

La table remplit chaque cellule : avec s de 25,000 lettres et t de 50,000, cela représente 1.25 × 10^9 cellules.

Algorithme

Créez une ligne prev de m+1 valeurs, toutes égales à true : un s vide correspond à chaque préfixe de t.
Pour chaque i de 1 à n, créez une ligne cur avec cur[0] = false.
Pour chaque j de 1 à m, définissez cur[j] comme cur[j-1], ou comme prev[j-1] lorsque s[i-1] est égal à t[j-1].
Remplacez prev par cur.
Renvoyez 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]

Deux pointeurs avec appariement glouton

Intuition

Gardez un pointeur i vers la prochaine lettre de s dont vous avez besoin, et prenez sa première occurrence dans t. Ce choix est sûr. Si un placement valide utilise une occurrence ultérieure de s[i], la remplacer par la première occurrence préserve l’ordre et laisse davantage de t pour le reste de s. Ainsi, si un placement existe, l’approche gloutonne le trouvera.

La boucle lit chaque lettre de t au plus une fois et conserve deux index : temps O(n + m) et mémoire O(1).

Algorithme

Définissez i = 0 pour s et j = 0 pour t.
Tant que les deux indices sont à l’intérieur de leurs chaînes, comparez s[i] à t[j].
S’ils sont égaux, augmentez i.
Augmentez j dans tous les cas.
Retournez si i est égal à la longueur 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)

Pièges et cas limites

Rechercher chaque lettre de s n’importe où dans t au lieu de poursuivre après la correspondance précédente. Cela accepte aec dans abcde.
Utiliser deux fois la même occurrence d’une lettre. noon n’est pas une sous-séquence de moon : son unique n, à l’index 3, ne peut pas être à la fois la première et la dernière lettre.
Renvoyer si j a atteint la fin de t. La boucle se termine souvent à cet endroit, que s ait été trouvé ou non ; seul i vous l’indique.
Ne pas s’arrêter lorsque t est épuisé. abc comparé à ab doit renvoyer false.
Lire s[i] après que i a atteint la fin de s. En Python ou en Java, cette lecture déclenche une exception : vérifiez donc i avant de comparer.

Questions fréquentes3

Quelle est la complexité temporelle de Is Subsequence ?

La solution à deux pointeurs s’exécute en O(n + m) temps, où n et m sont les longueurs de s et t, avec une mémoire supplémentaire de O(1). La boucle s’arrête après au plus m étapes. La table des préfixes nécessite un temps de O(n × m).

Quel est le lien entre Is Subsequence et la plus longue sous-séquence commune ?

s est une sous-séquence de t exactement lorsque leur plus longue sous-séquence commune a une longueur de n, soit la longueur totale de s. Le tableau des préfixes de la première approche est celui que tu construis pour ce problème. Ici, tu as seulement besoin de savoir si tout s tient, donc un parcours glouton suffit.

Quelle est la différence entre une sous-séquence et une sous-chaîne ?

Une sous-chaîne est un bloc de lettres consécutives, tandis qu’une sous-séquence peut sauter des lettres tant que l’ordre reste le même. ace est une sous-séquence de abcde, mais pas une sous-chaîne de celui-ci. Toute sous-chaîne est une sous-séquence, mais l’inverse n’est pas vrai.

def isSubsequence(s, t):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

s = "ace"
t = "abcde"

Résultat attendu

true