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 , et utilise O(1) mémoire supplémentaire. En pratique, la boucle s’arrête après au plus m étapes. Le tableau des préfixes prend O(n × m) temps.

Q: Pourquoi l’approche gloutonne à deux pointeurs fonctionne-t-elle pour Is Subsequence ?

Faire correspondre une lettre de s à sa position la plus précoce possible dans t laisse la plus longue partie possible de t pour les lettres restantes. Toute position qui utilise une occurrence ultérieure peut être modifiée pour utiliser l’occurrence précédente sans rompre l’ordre ; ainsi, s’il existe une position possible, la méthode gloutonne la trouve.

Q: Comment vérifier rapidement plusieurs chaînes avec le même t ?

Prépare t une seule fois : pour chaque lettre, stocke la liste triée des index où elle apparaît. Pour placer s[i] , effectue une recherche binaire dans la liste de cette lettre afin de trouver le premier index après la correspondance précédente. Chaque vérification coûte alors O(n log m) au lieu de O(m) .

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 écarts

Contraintes

1 ≤ s.length ≤ 3 × 10⁴
1 ≤ t.length ≤ 5 × 10⁴
s et t ne contiennent que des lettres minuscules de l’alphabet anglais.

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 contient 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 entre les deux sont supprimées.

+20 tests cachés à la soumission

Pour aller plus loin

Supposons que t reste inchangé et que tu doives vérifier un million de chaînes différentes s par rapport à lui. Comment préparerais-tu t pour que chaque vérification soit plus rapide que de relire 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 ignorer des lettres de t n’importe où, ce qui peut donner l’impression qu’il faut essayer de nombreuses façons de placer s dans t. Ce n’est pas nécessaire. Faire correspondre chaque lettre de s au premier endroit où elle peut aller n’est jamais moins avantageux qu’un autre choix, et transforme la recherche en un seul parcours de gauche à droite avec deux pointeurs.

Programmation dynamique sur les préfixes

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Pose une question plus petite : les i premières lettres de s peuvent-elles tenir dans les j premières lettres de t ? Appelons la réponse dp[i][j]. Si elles tiennent dans t[:j-1], elles tiennent aussi dans t[:j], puisque tu peux supprimer t[j-1]. Si s[i-1] est égal à t[j-1], tu peux aussi utiliser cette lettre, et les i-1 premières lettres de s doivent alors tenir dans t[:j-1]. Donc dp[i][j] = dp[i][j-1] or (s[i-1] == t[j-1] and dp[i-1][j-1]), et le préfixe vide de s tient partout.

La ligne i ne lit que la ligne i-1, donc deux lignes de longueur m+1 suffisent. La réponse se trouve dans la dernière cellule de la dernière ligne.

C’est la même table que celle que tu construis pour la plus longue sous-séquence commune, et elle est correcte, mais elle remplit chaque cellule. Avec s de 25 000 lettres et t de 50 000, cela représente 1.25 × 10^9 cellules, bien plus que ce qu’exige un seul passage sur les deux chaînes.

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] à cur[j-1], ou à prev[j-1] lorsque s[i-1] est égal à t[j-1].
Remplacez prev par cur.
Retournez 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

Parcourez t de gauche à droite et gardez un pointeur i vers la prochaine lettre de s qu’il vous reste à trouver. Lorsque t[j] est égal à s[i], utilisez-le et avancez i. Dans tous les cas, avancez j. Si i atteint la fin de s, chaque lettre a trouvé sa place dans l’ordre.

Pourquoi peut-on prendre sans risque la première correspondance ? Supposons qu’un placement valide utilise une occurrence ultérieure de s[i]. En la remplaçant par la première occurrence, on conserve l’ordre et il reste davantage de lettres de t à droite pour le reste de s ; le choix glouton ne fait donc jamais perdre un placement existant. Pour moon dans monsoon, le pointeur prend le o à l’index 1, ignore n et s, prend le o à l’index 4 et s’arrête sur le n à l’index 6.

j parcourt chaque lettre de t une seule fois et i avance uniquement, donc la boucle s’exécute au plus m fois. Deux index suffisent comme mémoire.

Algorithme

Définis i = 0 pour s et j = 0 pour t.
Tant que les deux index sont dans leurs chaînes, compare s[i] à t[j].
S’ils sont égaux, incrémente i.
Incrémente j dans tous les cas.
Renvoie 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

La boucle à deux pointeurs est courte, et ses bogues se nichent dans les cas limites.

Chercher chaque lettre de s n’importe où dans t au lieu de la chercher après la correspondance précédente. Cela accepte aec dans abcde, alors que l’ordre n’est pas respecté.
Utiliser deux fois la même occurrence d’une lettre. noon n’est pas une sous-séquence de moon : moon ne contient qu’un seul n, à l’index 3, et il ne peut pas être à la fois la première et la dernière lettre de noon.
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 le dit.
Oublier que s peut être plus long que t. Pour abc comparé à ab, il faut renvoyer false, ce que fait la boucle à condition qu’elle s’arrête quand t est épuisé.
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équentes4

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, et utilise O(1) mémoire supplémentaire. En pratique, la boucle s’arrête après au plus m étapes. Le tableau des préfixes prend O(n × m) temps.

Pourquoi l’approche gloutonne à deux pointeurs fonctionne-t-elle pour Is Subsequence ?

Faire correspondre une lettre de s à sa position la plus précoce possible dans t laisse la plus longue partie possible de t pour les lettres restantes. Toute position qui utilise une occurrence ultérieure peut être modifiée pour utiliser l’occurrence précédente sans rompre l’ordre ; ainsi, s’il existe une position possible, la méthode gloutonne la trouve.

Comment vérifier rapidement plusieurs chaînes avec le même t ?

Prépare t une seule fois : pour chaque lettre, stocke la liste triée des index où elle apparaît. Pour placer s[i], effectue une recherche binaire dans la liste de cette lettre afin de trouver le premier index après la correspondance précédente. Chaque vérification coûte alors O(n log m) au lieu de O(m).

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.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

s = "ace"
t = "abcde"

Attendu

true