题目描述:
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).
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).
题目大意:
给定一组没有重复的单词,从中寻找所有可能的“四方连词”。
一组单词如果其第k行和第k列组成的单词相同,其中0 ≤ k < max(numRows, numColumns),则称其为一个“四方连词”。
例如,单词序列["ball","area","lead","lady"]组成一个“四方连词”,因为每一行每一列的单词读起来都是一样的。
b a l l a r e a l e a d l a d y
注意:
- 单词个数在[1, 1000]之间
- 所有单词的长度均相同
- 单词长度在[1, 5]之间
- 每个单词只包含小写字母a-z
解题思路:
深度优先搜索(DFS)+ 剪枝(Pruning)
首先构建一个单词前缀prefix->单词word的字典mdict 深度优先搜索search(word, line),其中word是当前单词,line是行数 利用变量matrix记录当前已经生成的单词 前缀prefix = matrix[0..line][line],如果prefix对应单词不存在,则可以剪枝 否则枚举mdict[prefix],并递归搜索
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):
mdict[word[:i]].add(word)
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
本文链接:http://bookshadow.com/weblog/2016/10/16/leetcode-word-squares/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。
chris 发布于 2016年10月22日 10:59 #
第20行貌似应该是:prefix = ''.join(matrix[x][line-1] for x in range(line))。因为你从第“1”行开始
chris 发布于 2016年10月22日 11:04 #
啊没有,原代码是对的,游客没法删评论,你帮我删了吧,哈哈,多谢~