Hello les grinders,
Cette semaine, on continue notre lancée sur le backtracking, avec le problème 140. Word Break II 🔗.
Voici l’énoncé:
Étant donné une string
s
et un dictionnaire de motswordDict
, insérez des espaces danss
pour construire une phrase où chaque mot est présent danswordDict
. Retournez toutes ces phrases possibles, dans n'importe quel ordre.Un mot présent dans
wordDict
peut être réutilisé plusieurs fois pour construire une phrase.
🔔 - Comme la semaine dernière, l’énoncé insiste sur trouver toutes les phrases possibles, et non produire une solution très optimisée. Cela fait appel au backtracking pour résoudre ce problème. Le backtracking nous permet en effet d’explorer complètement un espace de solutions, et uniquement retenir celles respectant les contraintes de l’énoncé.
L’approche backtracking
Bien que l’énoncé paraisse différent, une structure backtracking identique à celle de la semaine dernière (39. Combination Sum) est parfaitement valide pour résoudre ce problème:
def word_break(s: str, word_dict: List[str]) -> List[str]: | |
word_dict, sentences, n = set(word_dict), [], len(s) | |
def backtrack(start: int, cur: List[str]) -> None: | |
if start == n: # solution valide, on la retient | |
sentences.append(' '.join(cur)) | |
return | |
for i in range(start + 1, n + 1): | |
if s[start: i] in word_dict: | |
# cette solution respecte les contraintes, | |
# on peut continuer à explorer les solutions suivantes | |
backtrack(i, cur + [s[start: i]]) | |
backtrack(0, []) | |
return sentences |
Avec quelques détails:
On utilise une liste
sentences
pour sauvegarder les solutions valides au fur et à mesure qu’on explore l’espace de recherche.On caste la liste
word_dict
en un set, pour bénéficier d’un lookup en O(1).La fonction inline backtrack:
- Parcourt la strings
de gauche à droite: on commence donc avec un indexstart
à 0,
- Ne met à jour cet indexstart
uniquement si la section de la string s que l’on vient de parcourir est un mot présent dansword_dict
, et récurse alors, pour explorer les phrases que l’on peut construire avec ce mot et le reste de la strings
,
- Sauvegarde la solution actuelle dans une listecur
, qui est copiée danssentences
si l’on arrive à la fin des
.Le slicing des string en Python permet d’écrire un code très concis.
Complexité
Pour chacun des N caractères présents dans s, nous avons 2 choix:
Insérer un espace, et commencer ainsi un nouveau mot avec le prochain caractère,
Ne pas insérer un espace, continuant ainsi le mot actuel.
Cela mène à une complexité exponentielle O(2^N). Les opérations de copie et slicing de string en Python sont faites en O(N) - négligeable devant O(2^N) mais à ne pas oublier. Mentionner cela lors de l’interview montrera que vous avez une bonne connaissance de Python.
Pour l’espace, étant donné que la fonction backtrack est récursive, nous utilisons la call stack pour stocker les résultats intermédiaires. Nous récursons au maximum N fois (une fois par caractère) et stockons jusqu’à N caractères à chaque appel. Cela donne ainsi une utilisation quadratique de la mémoire.
Conclusion
Voici le gist du stream pour avoir un walkthrough plus détaillé 👇
La semaine prochaine, on s’attaque au problème 692. Top K Frequent Words 🔗, pour s’entrainer avec la data structure Trie.
Comme d’habitude, on se donne rendez-vous à 09h30 samedi matin prochain sur notre channel Twitch pour traiter ce problème en live ⏱
See ya!
Photo de thumbnail de Matt Hardy