Étant donné un tableau arr[] composé de N des chaînes et une chaîne S si taille M, la tâche consiste à trouver la plus petite chaîne lexicographiquement constituée de la chaîne S comme préfixe. S’il n’existe aucune chaîne commençant par le préfixe S puis imprimer « -1 ».
Exemples:
Saisir: arr[] = {« pomme », « app », « apl », « aapl », « appax »}, S = « app »
Sortir: appax
Explication:
L’ordre lexicographique des chaînes constituées de « app » comme sous-chaîne est {« aapl », « apl », « appax », « appe », « apple »}. La plus petite chaîne lexicographique contenant est « appax ».
Saisir: arr[] = {« peut », « homme », « va »}, S = « fourgon »
Sortir: -1
Approcher: Le problème donné peut être résolu en triant le tableau de chaînes donné arr[] telle que toutes les chaînes commençant par des préfixes S se produire consécutivement. Parcourez maintenant le tableau de chaînes donné arr[] et lorsque la première chaîne dont le préfixe correspond à S puis imprimez cette chaîne et sortez de la boucle. Sinon, imprimez « -1 ».
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
C++
|
#include en utilisant l’espace de noms std ; bool is_prefix(chaîne temp, chaîne str) { if (temp.length() < str.length()) renvoie 0 ; autre { pour (entier i = 0 ; i < str.longueur(); i++) { si (chaîne[i] != température[i]) renvoie 0 ; } retour 1 ; } } chaîne lexicographiquementChaîne( entrée de chaîne[], int n, chaîne str) { sort(entrée, entrée + n); pour (int i = 0; i < n; i++) { chaîne temp = entrée[i]; if (est_prefix(temp, str)) { température de retour ; } } renvoie « -1 » ; } int main() { chaîne arr[] = { « pomme », « app », « apl », « aapl », « appax » } ; chaîne S = « application » ; entier N = 5; cout << chaîne lexicographique ( arr, N, S); renvoie 0 ; } |
Complexité temporelle : O(M*K*N*log N), où K est le maximum longueur de la chaîne dans le tableau arr[].
Espace auxiliaire : AU)
Une autre approche : L’approche ci-dessus peut également être optimisée en utilisant la structure de données Trie en insérant toutes les chaînes données dans le Trie, puis en vérifiant la première chaîne qui existe dans le Trie ayant le préfixe S.
Complexité temporelle : O(M*N)
Espace auxiliaire : AU)
Attention lecteur ! N’arrêtez pas d’apprendre maintenant. Obtenez tous les concepts importants de DSA avec le Cours auto-rythmé DSA à un prix adapté aux étudiants et devenez prêt pour l’industrie. Pour compléter votre préparation de l’apprentissage d’une langue à DS Algo et bien d’autres, veuillez vous référer Cours complet de préparation aux entretiens.
Au cas où vous souhaiteriez assister cours en direct avec des experts, veuillez vous référer Cours en direct DSA pour les professionnels en activité et Programmation compétitive en direct pour les étudiants.
