Skip to main content

Word Squares

Question​

None

Example 1
Input: ["AREA", "BALL", "DEAR", "LADY", "LEAD", "YARD"]

Output:
[
  ["AREA","BALL","DEAR","LADY"],
  ["BALL","DEAR","LADY","LEAD"],
  ["DEAR","LADY","LEAD","YARD"],
  ["LADY","LEAD","YARD","AREA"],
  ["LEAD","YARD","AREA","BALL"]
]

Solution​

all//Word Squares.py


def wordSquares(words):
    n = len(words[0])
    result = []

    def backtrack(square):
        if len(square) == n:
            result.append(square)
            return

        for word in words:
            if all(word.startswith(square[i][len(square)])
                    for i in range(len(square))):
                backtrack(square + [word])

    for word in words:
        backtrack([word])

    return result

words = ["area","lead","wall","lady","ball"]
print(wordSquares(words))