Welcome to Subscribe On Youtube
737. Sentence Similarity II
Description
We can represent a sentence as an array of words, for example, the sentence "I am happy with leetcode" can be represented as arr = ["I","am",happy","with","leetcode"].
Given two sentences sentence1 and sentence2 each represented as a string array and given an array of string pairs similarPairs where similarPairs[i] = [xi, yi] indicates that the two words xi and yi are similar.
Return true if sentence1 and sentence2 are similar, or false if they are not similar.
Two sentences are similar if:
- They have the same length (i.e., the same number of words)
sentence1[i]andsentence2[i]are similar.
Notice that a word is always similar to itself, also notice that the similarity relation is transitive. For example, if the words a and b are similar, and the words b and c are similar, then a and c are similar.
Example 1:
Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]] Output: true Explanation: The two sentences have the same length and each word i of sentence1 is also similar to the corresponding word in sentence2.
Example 2:
Input: sentence1 = ["I","love","leetcode"], sentence2 = ["I","love","onepiece"], similarPairs = [["manga","onepiece"],["platform","anime"],["leetcode","platform"],["anime","manga"]] Output: true Explanation: "leetcode" --> "platform" --> "anime" --> "manga" --> "onepiece". Since "leetcode is similar to "onepiece" and the first two words are the same, the two sentences are similar.
Example 3:
Input: sentence1 = ["I","love","leetcode"], sentence2 = ["I","love","onepiece"], similarPairs = [["manga","hunterXhunter"],["platform","anime"],["leetcode","platform"],["anime","manga"]] Output: false Explanation: "leetcode" is not similar to "onepiece".
Constraints:
1 <= sentence1.length, sentence2.length <= 10001 <= sentence1[i].length, sentence2[i].length <= 20sentence1[i]andsentence2[i]consist of lower-case and upper-case English letters.0 <= similarPairs.length <= 2000similarPairs[i].length == 21 <= xi.length, yi.length <= 20xiandyiconsist of English letters.
Solutions
-
class Solution { private int[] p; public boolean areSentencesSimilarTwo( String[] sentence1, String[] sentence2, List<List<String>> similarPairs) { if (sentence1.length != sentence2.length) { return false; } int n = similarPairs.size(); p = new int[n << 1]; for (int i = 0; i < p.length; ++i) { p[i] = i; } Map<String, Integer> words = new HashMap<>(); int idx = 0; for (List<String> e : similarPairs) { String a = e.get(0), b = e.get(1); if (!words.containsKey(a)) { words.put(a, idx++); } if (!words.containsKey(b)) { words.put(b, idx++); } p[find(words.get(a))] = find(words.get(b)); } for (int i = 0; i < sentence1.length; ++i) { if (Objects.equals(sentence1[i], sentence2[i])) { continue; } if (!words.containsKey(sentence1[i]) || !words.containsKey(sentence2[i]) || find(words.get(sentence1[i])) != find(words.get(sentence2[i]))) { return false; } } return true; } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } } -
class Solution { public: vector<int> p; bool areSentencesSimilarTwo(vector<string>& sentence1, vector<string>& sentence2, vector<vector<string>>& similarPairs) { if (sentence1.size() != sentence2.size()) return false; int n = similarPairs.size(); p.resize(n << 1); for (int i = 0; i < p.size(); ++i) p[i] = i; unordered_map<string, int> words; int idx = 0; for (auto e : similarPairs) { string a = e[0], b = e[1]; if (!words.count(a)) words[a] = idx++; if (!words.count(b)) words[b] = idx++; p[find(words[a])] = find(words[b]); } for (int i = 0; i < sentence1.size(); ++i) { if (sentence1[i] == sentence2[i]) continue; if (!words.count(sentence1[i]) || !words.count(sentence2[i]) || find(words[sentence1[i]]) != find(words[sentence2[i]])) return false; } return true; } int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } }; -
class Solution: def areSentencesSimilarTwo( self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]] ) -> bool: if len(sentence1) != len(sentence2): return False n = len(similarPairs) p = list(range(n << 1)) def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] words = {} idx = 0 for a, b in similarPairs: if a not in words: words[a] = idx idx += 1 if b not in words: words[b] = idx idx += 1 p[find(words[a])] = find(words[b]) for i in range(len(sentence1)): if sentence1[i] == sentence2[i]: continue if ( sentence1[i] not in words or sentence2[i] not in words or find(words[sentence1[i]]) != find(words[sentence2[i]]) ): return False return True -
var p []int func areSentencesSimilarTwo(sentence1 []string, sentence2 []string, similarPairs [][]string) bool { if len(sentence1) != len(sentence2) { return false } n := len(similarPairs) p = make([]int, (n<<1)+10) for i := 0; i < len(p); i++ { p[i] = i } words := make(map[string]int) idx := 1 for _, e := range similarPairs { a, b := e[0], e[1] if words[a] == 0 { words[a] = idx idx++ } if words[b] == 0 { words[b] = idx idx++ } p[find(words[a])] = find(words[b]) } for i := 0; i < len(sentence1); i++ { if sentence1[i] == sentence2[i] { continue } if words[sentence1[i]] == 0 || words[sentence2[i]] == 0 || find(words[sentence1[i]]) != find(words[sentence2[i]]) { return false } } return true } func find(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] }