Problème de segmentation de phrase — Word Break
Mostafa veut initier ses élèves à la traduction par une méthode simple et naïve qui est basée sur la décomposition de la phrase donnée en mots puis la traduction de chaque mot séparément et enfin la traduction de la phrase entière. Pour simplifier la traduction, Mostafa doit donner à ses élèves uniquement des phrases réalisables (phrases qui peuvent être construites à partir du dictionnaire) étant donné un dictionnaire de tous les mots possibles.
Le problème est que la phrase est sans espace, ce qui signifie qu'il n'y a pas d'espace entre les mots.
Aidez Mostafa en écrivant un programme qui détermine si la phrase donnée peut être construite à partir du dictionnaire donné.
Ce problème est un classique de la programmation dynamique et peut aussi être résolu par une approche récursive avec mémoïsation.
Énoncé du problème
Entrée
- La première ligne contient la phrase (sans espaces).
- La deuxième ligne contient tous les mots du dictionnaire, séparés par des espaces.
Sortie
- Oui si la phrase peut être construite à partir du dictionnaire donné.
- Non sinon.
meknesestunebellevilleaumaroc meknes fes marrakech ville maroc une est belle magnifique historique imperiale au
Oui
agadirestlacapitaledumaroc meknes fes marrakech ville maroc une est belle magnifique historique imperiale au
Non
- 1 ≤ longueur(phrase) ≤ 10³
- 1 ≤ nombre de mots dans le dictionnaire ≤ 10⁴
- Les mots sont composés de lettres minuscules.
Solution 1 — Approche récursive
L'idée est simple : nous considérons chaque préfixe et le recherchons dans le dictionnaire. Si le préfixe est présent dans le dictionnaire, nous recherchons le reste de la chaîne (ou suffixe).
Si l'appel récursif pour le suffixe retourne vrai, nous retournons vrai, sinon nous essayons le préfixe suivant. Si nous avons essayé tous les préfixes et qu'aucun d'entre eux n'a donné de solution, nous retournons Non.
estvalide("meknesest")
├── préfixe "m" (non dans dict)
├── préfixe "me" (non)
├── ...
├── préfixe "meknes" (✓ dans dict) → estvalide("est")
│ ├── préfixe "e" (non)
│ ├── préfixe "es" (non)
│ └── préfixe "est" (✓) → estvalide("") → true ✓
└── préfixe "meknese" (non)
└── ...#include <iostream>
#include <string>
#include <set>
#include <sstream>
using namespace std;
bool estvalide(string phrase, const set<string> &dictionnaire) {
int n = phrase.size();
if (n == 0)
return true;
for (int i = 1; i <= n; i++) {
string prefixe = phrase.substr(0, i);
if (dictionnaire.count(prefixe) > 0 &&
estvalide(phrase.substr(i, n - i), dictionnaire))
return true;
}
return false;
}
int main() {
string phrase, ligne_mots;
set<string> dictionnaire;
cin >> phrase;
// Sauter tous les espaces blancs de tête pour éviter le conflit avec getline
cin >> ws;
getline(cin, ligne_mots);
istringstream split(ligne_mots);
string mot;
while (split >> mot) {
dictionnaire.insert(mot);
}
if (estvalide(phrase, dictionnaire))
cout << "Oui" << endl;
else
cout << "Non" << endl;
return 0;
}import sys
def estvalide(phrase, dictionnaire):
n = len(phrase)
if n == 0:
return True
for i in range(1, n + 1):
if phrase[0:i] in dictionnaire and estvalide(phrase[i:], dictionnaire):
return True
return False
phrase = sys.stdin.readline().strip()
dictionnaire = set(sys.stdin.readline().strip().split())
if estvalide(phrase, dictionnaire):
print("Oui")
else:
print("Non")Complexité temporelle : O(2ⁿ) — exponentielle (pire cas).
Complexité spatiale : O(n) — profondeur de la pile d'appels.
Cette solution naïve recalcule plusieurs fois les mêmes sous-problèmes, ce qui la rend inefficace pour de longues phrases.
Solution 2 — Programmation Dynamique
Le problème ci-dessus présente des sous-problèmes qui se chevauchent. Nous pouvons donc résoudre le problème en utilisant la programmation dynamique.
dp[n+1] où :dp[i] = true si la sous-chaîne phrase[0..i-1] (les i premiers caractères) peut être segmentée en mots du dictionnaire.dp[0] = true (chaîne vide).Pour chaque position i de 1 à n, on cherche s'il existe une position j (0 ≤ j < i) telle que :
dp[j] = true(le préfixe phrase[0..j-1] est segmentable)- et
phrase[j..i-1](le suffixe) est dans le dictionnaire
Si une telle position existe, alors dp[i] = true.
Illustration — phrase = "meknesest", dictionnaire = {meknes, est}
| i | caractère | dp[i] | explication |
|---|---|---|---|
| 0 | - | ✓ | base (chaîne vide) |
| 1 | m | ✗ | "m" pas dans dictionnaire |
| 2 | e | ✗ | "me" pas dans dictionnaire |
| 3 | k | ✗ | "mek" pas dans dictionnaire |
| 4 | n | ✗ | "mekn" pas dans dictionnaire |
| 5 | e | ✗ | "mekne" pas dans dictionnaire |
| 6 | s | ✓ | "meknes" dans dictionnaire (j=0, dp[0]=✓) |
| 7 | e | ✗ | aucun j valide trouvé |
| 8 | s | ✗ | "es" pas dans dictionnaire |
| 9 | t | ✓ | "est" dans dictionnaire (j=6, dp[6]=✓) |
dp[9] = true → Oui
#include <iostream>
#include <string>
#include <cstring>
#include <set>
#include <sstream>
using namespace std;
bool estvalide(string phrase, const set<string> &dictionnaire) {
int n = phrase.size();
if (n == 0)
return true;
// dp[i] sera true si phrase[0..i-1] peut être segmentée en mots du dictionnaire
bool dp[n + 1];
memset(dp, false, sizeof(dp));
dp[0] = true; // chaîne vide
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
// Si le préfixe phrase[0..j-1] est segmentable et que
// phrase[j..i-1] est dans le dictionnaire
if (dp[j] && dictionnaire.count(phrase.substr(j, i - j)) > 0) {
dp[i] = true;
break; // pas besoin de continuer à chercher
}
}
}
return dp[n];
}
int main() {
string phrase, ligne_mots;
set<string> dictionnaire;
cin >> phrase;
// Sauter tous les espaces blancs de tête pour éviter le conflit avec getline
cin >> ws;
getline(cin, ligne_mots);
istringstream split(ligne_mots);
string mot;
while (split >> mot) {
dictionnaire.insert(mot);
}
if (estvalide(phrase, dictionnaire))
cout << "Oui" << endl;
else
cout << "Non" << endl;
return 0;
}import sys
def estvalide(phrase, dictionnaire):
n = len(phrase)
if n == 0:
return True
# dp[i] sera True si phrase[0..i-1] peut être segmentée en mots du dictionnaire
dp = [False] * (n + 1)
dp[0] = True # chaîne vide
for i in range(1, n + 1):
for j in range(i):
# Si le préfixe phrase[0..j-1] est segmentable et que
# phrase[j..i-1] est dans le dictionnaire
if dp[j] and phrase[j:i] in dictionnaire:
dp[i] = True
break # pas besoin de continuer à chercher
return dp[n]
phrase = sys.stdin.readline().strip()
dictionnaire = set(sys.stdin.readline().strip().split())
if estvalide(phrase, dictionnaire):
print("Oui")
else:
print("Non")Oui
| Critère | Solution récursive naïve | Programmation dynamique |
|---|---|---|
| Temps | O(2ⁿ) — exponentiel | O(n²) ou O(n × L) avec recherche optimisée |
| Espace | O(n) — pile d'appels | O(n) — tableau 1D |
| Sous-problèmes recalculés | Oui — nombreux recalculs | Non — mémoïsation implicite |
On peut optimiser la recherche en utilisant un trie (arbre de préfixes) pour vérifier si une sous-chaîne est dans le dictionnaire en temps linéaire en la longueur du mot, plutôt que d'utiliser un set qui nécessite de créer la sous-chaîne à chaque fois.
Autre optimisation : ne considérer que les longueurs de mots présentes dans le dictionnaire, ce qui peut réduire la complexité si les mots sont courts.
- Le problème de segmentation de phrase (Word Break) consiste à déterminer si une chaîne peut être décomposée en mots d'un dictionnaire.
- La solution récursive naïve a une complexité exponentielle O(2ⁿ).
- La programmation dynamique permet de résoudre le problème en temps polynomial O(n²) avec un espace O(n).
- L'approche dynamique utilise un tableau 1D où dp[i] indique si le préfixe de longueur i est segmentable.
- La relation de récurrence : dp[i] = true s'il existe j < i tel que dp[j] = true et phrase[j..i-1] ∈ dictionnaire.
- Ce problème est une application classique de la programmation dynamique sur les chaînes de caractères.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.