狗家店面

shuaiwa 发表于 2018-4-28 04:54
乐扣原题还是简单版的， follow up是加传递性吧

求leetcode题号~大神~

shufezq 发表于 2018-4-28 04:59
一段时间没刷题了，leetcode是不是有个同义词的题目是这个意思？ 用hashmap加dfs或者union find可解，lz的b ...

这个题楼主好像没有说可以传递，如果不可以传递，union find就不适用了吧~

假设有传递性：
class Solution:
    def isSynonym(self, syn, queries):

        parentWord = {}

        for i, s in enumerate(syn):
            self.union(s[0], s[1], parentWord)

        res = []

        for query1, query2 in queries:
            wordList1 = query1.split()
            wordList2 = query2.split()
            if len(wordList1) != len(wordList2):
                res.append(False)
                continue
            flag = 0
            for word1, word2 in zip(wordList1, wordList2):
                if self.find(word1, parentWord) != self.find(word2, parentWord):
                    res.append(False)
                    flag = 1
                    break

            if not flag:
                res.append(True)

        return res

    def find(self, word, parentWord):
        if word not in parentWord:
            parentWord[word] = word
            return word
        tmp = word
        while parentWord[word] != word:
            word = parentWord[word]
        parentWord[tmp] = word
        return word

    def union(self, word1, word2, parentWord):
        pword1 = self.find(word1, parentWord)
        pword2 = self.find(word2, parentWord)
        parentWord[pword1] = pword2

面试官给提示吗？

辛苦小农民 发表于 2018-4-28 06:01
面试官给提示吗？

嗯嗯，不懂就问

idatascience 发表于 2018-4-28 04:58
请问楼主follow up是什么呀？

因为我的做法如果有重复的词在dictionary会有些问题所以要我解决那个问题。当时真的紧张脑袋一片空白了

这个不是union find的问题么？
可以去搜搜利口 sentence similarity