LC: 737. Sentence Similarity II
https://leetcode.com/problems/sentence-similarity-ii/
737. Sentence Similarity II
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:
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.
The Essence:
Die Transitivität und Symmetrie der "Ähnlichkeits"-Beziehung der Wörter sollte implizieren, dass sie als Graph dargestellt werden können. Wenn die Verbindungen der Wortpaare als Graph dargestellt werden, ist es einfacher, das Problem entweder durch Tiefensuche oder Union-Find zu lösen. Im gesuchten Algorithmus werden zwei Hauptfragen gestellt, um zu entscheiden, ob die gegebenen Sätze ähnlich sind: 1- Haben die Sätze die gleiche Anzahl von Wörtern? 2- Sind die Wörter (am gleichen Index der gegebenen Sätze) ähnlich? Für Tiefensuche ist die 2. Frage dazu gleich: Enthält der Graph, der ein der Wörter enthält, auch das andere Wort? Für Union-Find-Technik ist die 2. Frage dazu gleich: Haben die Mengen, die die zwei Wörter enthalten, die gleiche Wurzel?
Details:
Für die DFS-Implementierung kann eine Hashtabelle von Listen verwendet werden, um auf die Nachbarn eines Strings zuzugreifen. Alle Strings können zur weiteren einfacheren Verwendung auch mit einer Zahl bzw. einem Index gezeigt werden, was besonders in der Union-Find-Technik geeignet ist.
Solution(s):
Default Code:
Last updated