Collar button LintCode algorithm question answer - 856 Sentence similarity

Collar button LintCode algorithm question answer - 856 Sentence similarity

856. Sentence similarity

Given two sentences words1 and words2 (each represented by a string array) and a similar word pair array pairs, you need to judge whether the two sentences are similar.

For example, if similar word pairs are pairs = [["great", "fine"], ["acting", "drama"], ["skills", "talent"]], then words1 = great acting skills and words2 = fine drama talent are similar.

Note that similar relationships are not transitive. For example, if "great" and "fine" are similar, "fine" and "good" are similar, "great" and "good" are not necessarily similar.

However, similarity is symmetrical. For example, if "great" is similar to "fine", then "fine" and "great" are also similar. The two are equivalent.

In addition, a word is always similar to itself. For example, the sentences words1 = ["great"], words2 = ["great"], pairs = [] are similar, although there are no similar word pairs.

Finally, two sentences can be similar only if the number of words is equal. Therefore, the sentence words1 = ["great"] can never be similar to the sentence words2 = ["doubleplus", "good"].

The length of words1 and words2 will not exceed 1000.
pairs will not be longer than 2000.
The length of each pair [i] is 2.
The length of each word [i] and pairs[i][j] is in the range of [1,20].

Example 1:

Input: words1 = ["great", "acting", "skills"], words2 = ["fine", "drama", "talent"] and pairs = ["great", "fine"], ["drama", "acting"], ["skills", "talent"]]
Output: true
Explanation:
"great" is similar to "fine"
"acting" is similar to "drama"
"skills" is similar to "talent"

Example 2:

Input: words1 = ["fine", "skills", "acting"], words2 = ["fine", "drama", "talent"] and pairs = ["great", "fine"], ["drama", "acting"], ["skills", "talent"]]
Output: false
Explanation:
"Fine" and "fine" are the same
"skills" and "drama" are not similar
'acting' and 'talent' are not similar

Problem solution

public class Solution {
    /**
     * @param words1: a list of string
     * @param words2: a list of string
     * @param pairs: a list of string pairs
     * @return: return a boolean, denote whether two sentences are similar or not
     */
    public boolean isSentenceSimilarity(String[] words1, String[] words2, List<List<String>> pairs) {
        // write your code here
        if (words1 == null
            || words2 == null) {
            return false;
        }
        if (words1.length != words2.length) {
            return false;
        }
        Map<String, Set<String>> pairsMap = new HashMap<>();
        for (List<String> pairsStrings : pairs) {
            for (String ps : pairsStrings) {
                Set<String> pairsSet = pairsMap.get(ps);
                if (pairsSet == null) {
                    pairsSet = new HashSet<>();
                    pairsMap.put(ps, pairsSet);
                }
                pairsSet.addAll(pairsStrings);
            }
        }
        for (int i = 0; i < words1.length; i++) {
            String word1 = words1[i];
            String word2 = words2[i];
            if (!word1.equals(word2)) {
                Set<String> pairsSet = pairsMap.get(word1);
                if (pairsSet == null
                    || !pairsSet.contains(word2)) {
                    pairsSet = pairsMap.get(word2);
                    if (pairsSet == null
                        || !pairsSet.contains(word1)) {
                        return false;
                    }
                }
            }
        }

        return true;
    }
}

Link to the original question here

Acknowledge

Thank you very much for taking the time to read this article. My level is limited. If there is anything wrong, please correct it.
Welcome to leave a message for discussion. I hope you can make a little progress every day.

Tags: Algorithm

Posted by zipdisk on Sun, 15 May 2022 14:16:07 +0300