Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/1258.html
You are given a list of equivalent string pairs synonyms
where synonyms[i] = [si, ti]
indicates that si
and ti
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 <= si.length, ti.length <= 10
si != ti
text
consists of at most10
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 }