SentenceSimilarity [source code]

public class SentenceSimilarity {
static
/******************************************************************************/
class Solution {
    public boolean areSentencesSimilar(String[] words1, String[] words2, String[][] pairs) {
        if (words1.length != words2.length)
            return false;
        if (words1.length == 0)
            return true;
        Map<String, Set<String>> dict = new HashMap<> ();
        for (String word : words1)
            dict.computeIfAbsent (word, s -> new HashSet<> ()).add (word);
        for (String word : words2)
            dict.computeIfAbsent (word, s -> new HashSet<> ()).add (word);
        for (String pair[] : pairs) {
            assert pair.length == 2;
            // [0] does not necessarily corresponds to WORDS1, [1] not necessarily WORDS2
            dict.computeIfAbsent (pair[0], s -> new HashSet<> ()).add (pair[1]);
            dict.computeIfAbsent (pair[1], s -> new HashSet<> ()).add (pair[0]);
        }
        for (int i = 0; i < words1.length; i++) {
            if (!dict.get (words1[i]).contains (words2[i]))
                return false;
        }
        return true;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SentenceSimilarity.Solution tester = new SentenceSimilarity.Solution();
        String[][][] inputs = {
            {{"great","acting","skills"}, {"fine","drama","talent"}, {"true"}}, {{"great","fine"},{"drama","acting"},{"skills","talent"}},
        };

        for (int i = 0; i < inputs.length / 2; i++) {
            String[] words1 = inputs[2 * i][0], words2 = inputs[2 * i][1];
            boolean ans = inputs[2 * i][2][0].equals ("true");
            String[][] pairs = inputs[2 * i + 1];
            System.out.println (Printer.separator ());
            boolean output = tester.areSentencesSimilar (words1, words2, pairs);
            System.out.printf ("%s, %s and \n%s -> %s, expected: %b\n",
                Printer.array (words1), Printer.array (words2), Matrix.printMatrix (pairs), Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

题目读完感觉还是很简单的, 直接写; 毕竟是Google的题目, 还是要注意边界case;

题目倒是没有什么边界case, 也是比较快的写完了, 但是最后的速度只有71ms (4%), 这个就很尴尬了. 后来看了一下hint, 我这个算法应该是overkill了, 虽然这种preprocessing的思路总体上问题不大, 但是对这题来说根本没有这个必要; 不过回头想想, hint里面这个was a pair要怎么检验呢? 好像还是要preprocess?

另外, 我这里用类似Pintos lab4里面的思路, 对于self的处理, 是直接insert的做法; 当然这个题目因为比较简单, 也可以直接就不这样, 只是最后判断的时候, 把equals当成一个额外的special case就行了;

这个是editorial:

class Solution {  
    public boolean areSentencesSimilar(  
            String[] words1, String[] words2, String[][] pairs) {  
        if (words1.length != words2.length) return false;  

        Set<String> pairset = new HashSet();  
        for (String[] pair: pairs)  
            pairset.add(pair[0] + "#" + pair[1]);  

        for (int i = 0; i < words1.length; ++i) {  
            if (!words1[i].equals(words2[i]) &&  
                    !pairset.contains(words1[i] + "#" + words2[i]) &&  
                    !pairset.contains(words2[i] + "#" + words1[i]))  
                return false;  
        }  
        return true;  
    }  
}

速度是6(90). 看起来思路其实跟我的思路非常类似, 但是最后速度比我的快这么多, 很大一个原因就是因为避免了collection of collections这个坑. 所以Jason的观点还是要记住的; 至于这里这个string key的思路, 在NLP里面也是碰到过的;

discussion没有什么很特别的解法, 而且奇怪的是, 很多人都用了类似我的map of sets的思路;

submission里面的:

class Solution {  
    public boolean areSentencesSimilar(String[] words1, String[] words2, String[][] pairs) {  
        if (words1.length != words2.length) return false;  
        for (int i = 0; i < words1.length; i++) {  
            if (!similar(words1[i], words2[i], pairs)) {  
                return false;  
            }  
        }  
        return true;  
    }  

    private boolean similar(String s1, String s2, String[][] pairs) {  
        if (s1.equals(s2)) return true;  
        for (String[] pair : pairs) {  
            if (pair[0].equals(s1) && pair[1].equals(s2)) {  
                return true;  
            }  
            if (pair[0].equals(s2) && pair[1].equals(s1)) {  
                return true;  
            }  
        }  
        return false;  
    }  
}

这样看起来两重循环的算法, 居然都能跑到6(90), 很无语;

Problem Description

Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.

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

Note that the similarity relation is not transitive. For example, if "great" and "fine" are similar, and "fine" and "good" are similar, "great" and "good" are not necessarily similar.

However, similarity is symmetric. For example, "great" and "fine" being similar is the same as "fine" and "great" being similar.

Also, a word is always similar with itself. For example, the sentences words1 = ["great"], words2 = ["great"], pairs = [] are similar, even though there are no specified similar word pairs.

Finally, sentences can only be similar if they have the same number of words. So a sentence like words1 = ["great"] can never be similar to words2 = ["doubleplus","good"].

Note:

• The length of words1 and words2 will not exceed 1000.
• The length of pairs will not exceed 2000.
• The length of each pairs[i] will be 2.
• The length of each words[i] and pairs[i][j] will be in the range [1, 20].

Difficulty:Easy
Total Accepted:5.5K
Total Submissions:14.4K
Contributor:1337c0d3r
Companies
google
Related Topics
hash table
Similar Questions
Friend CirclesAccounts MergeSentence Similarity II

Hint 1
Two words w1 and w2 are similar if and only if w1 == w2, (w1, w2) was a pair, or (w2, w1) was a pair.