## 题目描述：

LeetCode 425. Word Squares

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:

1. There are at least 1 and at most 1000 words.
2. All words will have the exact same length.
3. Word length is at least 1 and at most 5.
4. Each word contains only lowercase English alphabet a-z.

Example 1:

```Input:

Output:
[
[ "wall",
"area",
],
[ "ball",
"area",
]
]

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).```

Example 2:

```Input:
["abat","baba","atan","atal"]

Output:
[
[ "baba",
"abat",
"baba",
"atan"
],
[ "baba",
"abat",
"baba",
"atal"
]
]

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).```

## 题目大意：

```b a l l
a r e a
l e a d
l a d y```

1. 单词个数在[1, 1000]之间
2. 所有单词的长度均相同
3. 单词长度在[1, 5]之间
4. 每个单词只包含小写字母a-z

## 解题思路：

```首先构建一个单词前缀prefix->单词word的字典mdict

## Python代码：

``````class Solution(object):
def wordSquares(self, words):
"""
:type words: List[str]
:rtype: List[List[str]]
"""
m = len(words)
n = len(words[0]) if m else 0
mdict = collections.defaultdict(set)
for word in words:
for i in range(n):
matrix = []
ans = []
def search(word, line):
matrix.append(word)
if line == n:
ans.append(matrix[:])
else:
prefix = ''.join(matrix[x][line] for x in range(line))
for word in mdict[prefix]:
search(word, line + 1)
matrix.pop()
for word in words:
search(word, 1)
return ans
``````

Pingbacks已关闭。

1. chris 发布于 2016年10月22日 10:59 #

第20行貌似应该是：prefix = ''.join(matrix[x][line-1] for x in range(line))。因为你从第“1”行开始

2. chris 发布于 2016年10月22日 11:04 #

啊没有，原代码是对的，游客没法删评论，你帮我删了吧，哈哈，多谢～