easy python Hashmap + DFS


  • 0
    L

    The idea get from https://discuss.leetcode.com/topic/63516/explained-my-java-solution-using-trie-126ms-16-16 post. but I choose hashmap instead of Trie tree.

    class Solution(object):
        def wordSquares(self, words):
            """
            :type words: List[str]
            :rtype: List[List[str]]
            """
            if words:
                prefix = collections.defaultdict(list)
                for w in words:
                    for i in range(len(w)):
                        prefix[w[:(i + 1)]].append(w)
                ret = []
                def search(temp):
                    l = len(temp)
                    if l == len(words[0]):
                        ret.append(temp)
                        return
                    pre = ''
                    for w in temp:
                        pre += w[l]
                    for w in prefix[pre]:
                        search(temp + [w])
                for w in words:
                    search([w])
                return ret
            return []
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.