Given a sentence and a set of synonym rules, return every sentence you can produce by replacing each rule-word with one of its options. Words without a rule stay as-is. Expand words left to right, trying options in the order given.
substituteSynonyms(sentence, rules)
Input format: sentence | rules, where rules are space-separated word=opt1,opt2
entries. Output sentences separated by ;.
"i love you", rules love=like,adore // → "i like you;i adore you"
"hi there", (no rules) // → "hi there"
This has the same shape as expanding parenthesized groups, except the units are whole words and the options come from a synonym lookup table rather than parentheses in the text. Whenever you see "for each position, choose one of several options, produce every combination," it's the same decision-tree pattern with a different source for the options.
Split the sentence into words — each is one decision point. A word with a rule offers its listed synonyms as options; a word without one has exactly one option: itself. Framing "no rule" as "a one-item option list" lets both cases share the same logic.
Each output sentence corresponds to one choice at every rule-bearing word (non-rule words contribute no real choice). Trying every option at the current word and pairing it with every completion of the rest explores the full Cartesian product across all words — nothing skipped, nothing duplicated.
Finding all rule-words first and looping over every combination with nested loops sized to however many exist requires knowing that count in advance and writing dynamically-sized loops — awkward. Recursing word by word sidesteps this: each call worries about one word and defers the rest's combinatorics to itself, the same trick as the parenthesized-groups problem, generalized from characters to words.
def substitute_synonyms(sentence, rules):
words = sentence.split()
def expand(i):
if i == len(words):
return [""]
options = rules.get(words[i], [words[i]])
suffixes = expand(i + 1)
result = []
for opt in options:
for suffix in suffixes:
result.append(opt if suffix == "" else opt + " " + suffix)
return result
return expand(0)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.