L’algorithme pour mettre les mots en gras en HTML

Étant donné un ensemble de mots-clés et une chaîne S, mettez toutes les apparitions de tous les mots-clés en S gras. Toutes les lettres entre les balises et deviennent en gras.

La chaîne renvoyée doit utiliser le moins de balises possible et, bien sûr, les balises doivent former une combinaison valide.

Par exemple, étant donné que mots = ["ab", "bc"] et S = "aabcd", nous devrions renvoyer "a abc d". Notez que renvoyer "a a bcd" utiliserait plus de balises, donc c’est incorrect.

Noter:

• mots a une longueur dans la plage [0, 50].
• mots[i] a une longueur dans la plage [1, 10].
• S a une longueur dans la plage [0, 500].
• Tous les caractères des mots [i] et S sont des lettres minuscules.

Rendre la chaîne en gras à l’aide de l’algorithme Bruteforce

Sans l’exigence du plus court, nous pouvons mettre en gras toutes les occurrences des mots de la liste. Comme on nous donne la chaîne HTML d’origine, nous pouvons marquer en gras pour chaque caractère qui apparaît dans les mots en gras.

Ainsi, avec l’espace O(N) et O(NM) où N est la taille de la chaîne et M est la longueur totale de la chaîne en gras, l’ algorithme de force brute C++ suivant insérera le moins de balises HTML en gras qui satisfont à l’exigence.

Une fois les caractères gras marqués, nous analysons à nouveau la chaîne et recherchons les limites, puis insérons les balises en conséquence.