given a set of words without duplicates find all word squares you can build from them a sequence of words forms a valid word square if the kth row and column read the exact same string where 0 k maxnumrows numcolumns for example the word sequence ball area lead lady forms a word square because each word reads the same both horizontally and vertically b a l l a r e a l e a d l a d y note there are at least 1 and at most 1000 words all words will have the exact same length word length is at least 1 and at most 5 each word contains only lowercase english alphabet az example 1 input area lead wall lady ball output wall area lead lady ball area lead lady explanation the output consists of two word squares the order of output does not matter just the order of words in each word square matters given a set of words without duplicates find all word squares you can build from them a sequence of words forms a valid word square if the kth row and column read the exact same string where 0 k max numrows numcolumns for example the word sequence ball area lead lady forms a word square because each word reads the same both horizontally and vertically b a l l a r e a l e a d l a d y note there are at least 1 and at most 1000 words all words will have the exact same length word length is at least 1 and at most 5 each word contains only lowercase english alphabet a z example 1 input area lead wall lady ball output wall area lead lady ball area lead lady explanation the output consists of two word squares the order of output does not matter just the order of words in each word square matters
import collections

def word_squares(words):
    n = len(words[0])
    fulls = collections.defaultdict(list)
    for word in words:
        for i in range(n):
            fulls[word[:i]].append(word)

    def build(square):
        if len(square) == n:
            squares.append(square)
            return
        prefix = ""
        for k in range(len(square)):
            prefix += square[k][len(square)]
        for word in fulls[prefix]:
            build(square + [word])
    squares = []
    for word in words:
        build([word])
    return squares