Word Squares – Python 3 (Week 12 – 19)

class Solution:
    """
    @param: words: a set of words without duplicates
    @return: all word squares
    """
        
    def initPrefix(self, words):
        for word in words:
            if '' not in self.hash:
                self.hash[''] = []
            self.hash[''].append(word)
            #self.hash[""] += [str(word)] 
                
            prefix = ''
            for c in word:
                prefix += c
                if prefix not in self.hash:
                    self.hash[prefix] = []
                self.hash[prefix].append(word)
                #self.hash[prefix] += [str(word)]
    
    def checkPrefix(self, x, nextWord, l):
        for i in range (x + 1, l):
            prefix = ''
            for item in self.path:
                prefix += item[i]
            prefix += nextWord[i]
            if prefix not in self.hash:
                return False
        return True
        
    def dfs(self, x, l):
        if x == l:
            self.ans.append(list(self.path)) #copy list
            #self.ans.append(self.path)
            return
        
        prefix = ""
        for item in self.path:
            prefix += item[x]
            
        for item in self.hash[prefix]:
            if not self.checkPrefix(x, item, l):
                continue
            self.path.append(item)
            self.dfs(x + 1, l)
            self.path.pop()
        
        
    def wordSquares(self, words):
        # write your code here
        self.hash = {}
        self.path = []
        self.ans = []
        
        if not words:
            return self.ans
        
        self.initPrefix(words)
        self.dfs(0, len(words[0]))
        
        return self.ans