Synonymous sentences
December 27, 2022
graphProblem URL: Synonymous sentences
We will create a graph where the nodes are the words and the edges are the synonyms. Then we will do a DFS to find all the possible sentences and add that to a hashset to remove duplicates. Finally, we will sort the sentences and return them.
class Solution:
def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]:
graph = collections.defaultdict(list)
for key, val in synonyms:
graph[key].append(val)
graph[val].append(key)
res = set()
stack = [text]
while stack:
sentence = stack.pop()
res.add(sentence)
words = sentence.split()
for i in range(len(words)):
if words[i] in graph:
for rw in graph[words[i]]:
newSentence = " ".join(words[:i] + [rw] + words[i+1:])
if newSentence not in res:
stack.append(newSentence)
return sorted(list(res))
Time complexity: O(n^2)
Space complexity: O(n^2)