String Formatting Challenge

MediumPython

Problem

The Ethos Life quote flow receives a lowercase phrase with spaces removed, along with the dictionary of valid words used to build it. Insert spaces to restore the original phrase.

Return one valid sentence containing the dictionary words in their original order. The input is guaranteed to have exactly one valid segmentation. If no segmentation exists, return an empty string.

Formal Specification

Implement restore_sentence(s, dictionary):

s is a lowercase string with no spaces.
dictionary is a list of distinct lowercase words.
Return a string formed by inserting single spaces between dictionary words.
Every character in s must belong to exactly one returned word.

Example 1:

Input: s = "hiplanetearth", dictionary = ["hi", "planet", "earth"]
Output: "hi planet earth"
Explanation: The string can be segmented as "hi" + "planet" + "earth".

Example 2:

Input: s = "ethoslifequote", dictionary = ["ethos", "life", "quote"]
Output: "ethos life quote"
Explanation: Each dictionary word matches the next portion of the input.

Constraints

1 <= len(s) <= 1000
1 <= len(dictionary) <= 5000
1 <= len(word) <= 100
All strings contain only lowercase English letters
The dictionary contains distinct words
The input has exactly one valid segmentation, or none

Function Signature

def restore_sentence(s, dictionary):