Comment déterminer si une chaîne est composée uniquement de lettres données par une seconde chaîne

Question

J'ai deux chaînes. Comment puis-je déterminer si la première chaîne est composée uniquement de lettres données par la deuxième chaîne?

Par exemple:

A = abcd 
B = abbcc 

REVERSE faux, puisque d est pas dans la deuxième chaîne.

A = aab 
B = ab 

doit retourner vrai.

Si le programme renvoie la plupart du temps faux, comment puis-je optimiser ce programme? Si ça revient vrai la plupart du temps, comment puis-je l'optimiser ensuite?

Answer 1

Triez les deux chaînes. Ensuite, passez par A, et passez par un pointeur B. Si le caractère de A est le même que celui sur lequel pointe le pointeur B, continuez à regarder A. Si le caractère de A est plus tard dans l'alphabet que le pointeur B pour avancer le pointeur B Si le caractère dans A est plus tôt dans l'alphabet que ce que pointe le pointeur B, renvoyez false. Si vous n'avez plus de A, renvoyez true.

Answer 2

> Si le programme retourne toujours faux, comment optimiser ce programme?

return false 

> Si c'est toujours vrai, comment l'optimiser?

return true 

EDIT: Sérieusement, il est une bonne question quel algorithme permet d'optimiser le cas de l'échec, et quel algorithme permet d'optimiser le cas de succès. Je ne sais pas quel algorithme strstr utilise, il peut s'agir d'un algorithme globalement bon qui n'est optimal pour aucune de ces hypothèses. Peut-être que vous allez attraper quelqu'un ici qui le sait de manière désinvolte. Sinon, cela ressemble à un bon endroit pour commencer la lecture: Exact String Matching Algorithms

Answer 3

[Comment] déterminer [si] la première chaîne [est composée de caractères qui apparaissent dans] la deuxième chaîne?

Voici un algorithme rapide:

1. Traiter les première et deuxième chaînes que deux ensembles de caractères S et T.
2. Exécuter le set differenceS - T. Appelez le résultat U.

Si U est non vide, renvoyer false. Sinon, renvoyez true.

Answer 4

Voici une manière simple.

def isComposedOf(A, B): 
    bset = set(B) 
    for c in A: 
     if c not in bset: 
      return False 
    return True 

Cet algorithme marche chaque chaîne une fois, il fonctionne en O (len (A) + len (B)) temps.

Lorsque la réponse est oui, vous ne pouvez pas faire mieux que des comparaisons len (A) même dans le meilleur des cas, car peu importe ce que vous devez vérifier chaque lettre.Et dans le pire des cas, l'un des caractères de A est caché très profondément dans B. Donc O (len (A) + len (B)) est optimal, en ce qui concerne les performances du pire cas. De même: lorsque la réponse est non, vous ne pouvez pas faire mieux que les comparaisons len (B) même dans le meilleur des cas; et dans le pire des cas, le caractère qui n'est pas dans B est caché très profondément dans A. Donc O (len (A) + len (B)) est de nouveau optimal.

Vous pouvez réduire le facteur constant en utilisant une meilleure structure de données pour bset. Vous pouvez éviter de balayer tout B dans certains cas (non pires) où la réponse est oui en le construisant paresseusement, en scannant plus de B chaque fois que vous trouvez un caractère dans A que vous n'aviez pas vu auparavant.

Answer 5

En supposant que les chaînes ont toutes les minuscules, vous pouvez alors avoir un vecteur de bit et définir le bit en fonction de la position position = str1[i] - 'a'. pour le définir vous le feriez
bitVector |= (1<<pos). Et puis pour str2 vous vérifieriez si un bit est défini dans bitVector pour tous les bits, si tel est le cas, renvoyez true sinon renvoyez false.