Question

Formatted question description: https://leetcode.ca/all/1258.html

You are given a list of equivalent string pairs synonyms where synonyms[i] = [s_i, t_i] indicates that s_i and t_i are equivalent strings. You are also given a sentence text.

Return all possible synonymous sentences sorted lexicographically.

Example 1:

Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"
Output: ["I am cheerful today but was sad yesterday","I am cheerful today but was sorrow yesterday","I am happy today but was sad yesterday","I am happy today but was sorrow yesterday","I am joy today but was sad yesterday","I am joy today but was sorrow yesterday"]

Example 2:

Input: synonyms = [["happy","joy"],["cheerful","glad"]], text = "I am happy today but was sad yesterday"
Output: ["I am happy today but was sad yesterday","I am joy today but was sad yesterday"]

Constraints:

0 <= synonyms.length <= 10
synonyms[i].length == 2
1 <= s_i.length,t_i.length <= 10
s_i != t_i
text consists of at most 10 words.
All the pairs of synonyms are unique.
The words of text are separated by single spaces.

Algorithm

Union search, recursive enumeration

O(2^n * L)

Use the union search to find the synonym group, and then recursively enumerate and replace the synonym.

Time complexity

The total time complexity of finding the synonym group is approximately O(n), and the time complexity of recursion is O(2^n * L), where L is the length of the string O(L) time is required for each word replacement).

Therefore, the total time complexity is O(2^n * L).

Space complexity

Union search requires O(n) space, and recording answers requires O(2^n * L) space, so the total space complexity is O(2^n * L).

Code

public class Synonymous_Sentences {

    class Solution {

        // word => its similar words set
        Map<String, Set<String>> map = new HashMap<>();
        List<String> res = new ArrayList<>();

        public List<String> generateSentences(List<List<String>> synonyms, String text) {

            //build graph.
            for (List<String> s : synonyms) {
                String a = s.get(0);
                String b = s.get(1);
                map.getOrDefault(a, new HashSet<>()).add(b);
                map.getOrDefault(b, new HashSet<>()).add(a);
            }

            String[] split = text.split("\\W+");
            helper(split, 0, "");

            Collections.sort(res);
            return res;
        }

        public void helper(String[] wordsArray, int index, String cur) {

            if (index == wordsArray.length) {
                res.add(cur);
                return;
            }

            if (map.containsKey(wordsArray[index])) {
                List<String> choices = new ArrayList<>();
                //find all synonyms related to s
                getSynonyms(wordsArray[index], new HashSet<>(), choices);

                //try to change word at index to every possible synonyms word
                for (String s : choices) {
                    helper(wordsArray, index + 1, cur + (index == wordsArray.length - 1 ? s : s + " "));
                }
            } else {
                //if the word at index has no synonyms, just go for next.
                helper(wordsArray, index + 1, cur + (index == wordsArray.length - 1 ? wordsArray[index] : wordsArray[index] + " "));
            }
        }

        //get all synonyms related to s
        public void getSynonyms(String s, Set<String> visited, List<String> choices) {
            choices.add(s);
            visited.add(s);
            for (String each : map.get(s)) {
                if (!visited.contains(each)) {
                    getSynonyms(each, visited, choices);
                }
            }
        }
    }
}

// OJ: https://leetcode.com/problems/synonymous-sentences/
// Time: O(NlogN)
// Space: O(N)
class UnionFind {
    vector<int> id;
public:
    UnionFind(int N) : id(N) {
        iota(begin(id), end(id), 0);
    }
    int find(int a) {
        return id[a] == a ? a : (id[a] = find(id[a]));
    }
    void connect(int a, int b) {
        id[find(a)] = find(b);
    }
};
class Solution {
public:
    vector<string> generateSentences(vector<vector<string>>& A, string s) {
        istringstream ss(s);
        string word;
        vector<string> v, tmp, ans;
        while (ss >> word) v.push_back(word);
        int id = 0;
        unordered_map<string, int> index;
        unordered_map<int, string> rindex;
        for (auto &syn : A) {
            if (index.count(syn[0]) == 0) {
                index[syn[0]] = id;
                rindex[id] = syn[0];
                ++id;
            }
            if (index.count(syn[1]) == 0) {
                index[syn[1]] = id;
                rindex[id] = syn[1];
                ++id;
            }
        }
        UnionFind uf(index.size());
        for (auto &syn : A) {
            uf.connect(index[syn[0]], index[syn[1]]);
        }
        unordered_map<int, set<string>> m;
        for (int i = 0; i < index.size(); ++i) {
            m[uf.find(i)].insert(rindex[i]);
        }
        function<void(int)> dfs = [&](int i) {
            if (i == v.size()) {
                string t;
                for (auto &w : tmp) {
                    if (t.size()) t += ' ';
                    t += w;
                }
                ans.push_back(t);
                return;
            }
            if (index.count(v[i])) {
                for (auto &syn : m[uf.find(index[v[i]])]) {
                    tmp.push_back(syn);
                    dfs(i + 1);
                    tmp.pop_back();
                } 
            } else {
                tmp.push_back(v[i]);
                dfs(i + 1);
                tmp.pop_back();
            }
        };
        dfs(0);
        return ans;
    }
};

'''
>>> a = [1,2,3]
>>> b = [4,5]
>>>
>>> a+b
[1, 2, 3, 4, 5]
>>>
>>> a.extend(b)
>>> a
[1, 2, 3, 4, 5]
>>>
>>> a = [1,2,3]
>>> a.append(b)
>>> a
[1, 2, 3, [4, 5]]
'''
class Solution:
    def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]:
        p = {} # parent[]

        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        for a, b in synonyms:
            p[a] = a
            p[b] = b
        for a, b in synonyms:
            p[find(a)] = find(b)

        s = defaultdict(set)
        for a, b in synonyms:
            s[find(a)].add(a)
            s[find(b)].add(b)
        res = []
        for word in text.split(' '):
            if word not in p:
                if not res:
                    res.append([word]) # append a list [word]
                else:
                    for a in res:
                        a.append(word)
            else:
                words = sorted(s[find(word)])
                if not res:
                    for b in words:
                        res.append([b])
                else:
                    res = [a + [b] for a in res for b in words]
        return [' '.join(sentence) for sentence in res]

############

from collections import defaultdict

# recursive
class Solution:
    def generateSentences(self, synonyms, text):
        def helper(words_array, index, cur):
            if index == len(words_array):
                res.append(cur)
                return

            if words_array[index] in synonyms_map:
                choices = []
                getSynonyms(words_array[index], set(), choices)

                for s in choices:
                    helper(
                        words_array,
                        index + 1,
                        cur + (s if index == len(words_array) - 1 else s + " "),
                    )
            else:
                helper(
                    words_array,
                    index + 1,
                    cur + (words_array[index] if index == len(words_array) - 1 else words_array[index] + " "),
                )

        def getSynonyms(s, visited, choices):
            choices.append(s)
            visited.add(s)
            for each in synonyms_map[s]:
                if each not in visited:
                    getSynonyms(each, visited, choices)

        synonyms_map = defaultdict(set)
        res = []
        for s in synonyms:
            a, b = s[0], s[1]
            synonyms_map[a].add(b)
            synonyms_map[b].add(a)

        words = text.split("\\W+")
        helper(words, 0, "")

        res.sort()
        return res

type unionFind struct {
	p, size []int
}

func newUnionFind(n int) *unionFind {
	p := make([]int, n)
	size := make([]int, n)
	for i := range p {
		p[i] = i
		size[i] = 1
	}
	return &unionFind{p, size}
}

func (uf *unionFind) find(x int) int {
	if uf.p[x] != x {
		uf.p[x] = uf.find(uf.p[x])
	}
	return uf.p[x]
}

func (uf *unionFind) union(a, b int) {
	pa, pb := uf.find(a), uf.find(b)
	if pa != pb {
		if uf.size[pa] > uf.size[pb] {
			uf.p[pb] = pa
			uf.size[pa] += uf.size[pb]
		} else {
			uf.p[pa] = pb
			uf.size[pb] += uf.size[pa]
		}
	}
}

func generateSentences(synonyms [][]string, text string) (ans []string) {
	ss := map[string]bool{}
	for _, pairs := range synonyms {
		ss[pairs[0]] = true
		ss[pairs[1]] = true
	}
	words := []string{}
	for w := range ss {
		words = append(words, w)
	}
	d := map[string]int{}
	for i, w := range words {
		d[w] = i
	}
	uf := newUnionFind(len(words))
	for _, pairs := range synonyms {
		uf.union(d[pairs[0]], d[pairs[1]])
	}
	g := make([][]int, len(words))
	for i := range g {
		g[uf.find(i)] = append(g[uf.find(i)], i)
	}
	for i := range g {
		sort.Slice(g[i], func(a, b int) bool { return words[g[i][a]] < words[g[i][b]] })
	}
	t := []string{}
	sentences := strings.Split(text, " ")
	var dfs func(int)
	dfs = func(i int) {
		if i >= len(sentences) {
			ans = append(ans, strings.Join(t, " "))
			return
		}
		if _, ok := ss[sentences[i]]; !ok {
			t = append(t, sentences[i])
			dfs(i + 1)
			t = t[:len(t)-1]
			return
		} else {
			for _, j := range g[uf.find(d[sentences[i]])] {
				t = append(t, words[j])
				dfs(i + 1)
				t = t[:len(t)-1]
			}
		}
	}
	dfs(0)
	return
}

1258 - Synonymous Sentences

Question

Algorithm

Time complexity

Space complexity

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Time complexity

Space complexity

Code

All Problems

All Solutions