Problem statement

https://leetcode.com/problems/synonymous-sentences/

Solution

We can separate algorithm in two parts:

  1. Traverse graph and create connected components, we can do this for example with dfs.
  2. For each word in text, check if we have it in components: if we do no have it, we have only one option, if we have it, we have all candidates from component. Then we use functionality of product to generate all answers.

Complexity

Time complexity of first part is O(E + n), however time complexity of the second part can be exponential: it can be O(m * 2^E), where m is length of text and E <= 10.

Code

class Solution:
    def generateSentences(self, synonyms, text):
        G, V, idx = defaultdict(list), set(), 0
        comps, comps_inv = defaultdict(list), {}
        for x, y in synonyms:
            G[x].append(y)
            G[y].append(x)

        def dfs(node, idx):
            V.add(node)
            comps[idx] += [node]
            comps_inv[node] = idx
            for child in G[node]:
                if child not in V:
                    dfs(child, idx)

        for node in G.keys():
            if node not in V:
                dfs(node, idx)
                idx += 1
                
        cands = []
        for word in text.split():
            if word in comps_inv:
                cands += [sorted(comps[comps_inv[word]])]
            else:
                cands += [[word]]
                
        return [" ".join(x) for x in product(*cands)]