在拼字游戏棋盘上找到所有单词

Question

有没有简单又快速的方法，可以获取放在拼字游戏棋盘上的所有单词？这个棋盘是用一个二维字符数组来表示的。

提前谢谢你！

Answer 1

如果我理解得没错的话，你可以试试这样做：

a = [['w','o','r','d'],
     ['i','p','o','d'],
     ['k','u','a','k'],
     ['i','s','d','s']]

lines = (''.join(line) for line in a)
rows = (''.join(line) for line in zip(*a))

print list(lines)
print list(rows)

Answer 2

在每一列从上到下查找连续的字符组合，然后在每一行从左到右查找相同的组合。这种方法的时间复杂度是O(n^2)，不过我觉得很难找到比这个更快的办法。

Answer 3

这和Artsiom的回答有点像，但考虑到了拼字游戏棋盘上单词之间会有空格的情况。

假设你的“二维字符数组”看起来是这样的：

board = [['s','t','a','c','k',' ',' ',' '],
         ['p',' ',' ','a',' ','c',' ',' '],
         ['o','v','e','r','f','l','o','w'],
         ['o',' ','a','t',' ','a',' ','a'],
         ['n','o','t',' ',' ','m','a','t'],
         [' ',' ','e',' ',' ',' ',' ','e'],
         [' ',' ','r',' ',' ',' ',' ','r'],
         [' ','e','y','e','s',' ',' ',' ']]

你可以这样做：

import itertools
rows = (''.join(row) for row in board)
columns = (''.join(column) for column in zip(*board))
words = [word for line in itertools.chain(rows,columns) for word in line.split() if len(word) > 1]

这样就会得到：

['stack', 'overflow', 'at', 'not', 'mat', 'eyes', 'spoon', 'eatery', 'cart', 'clam', 'water']

我们所做的就是把每一行和每一列的字符转换成像 'not mat' 这样的字符串，然后使用str.split()来去掉空格，这样就能得到一个单词的列表，同时把长度为一个字母的东西也去掉。

使用itertools.chain()可以让我们在一个列表推导式中同时遍历行和列。

在拼字游戏棋盘上找到所有单词

3 个回答

撰写回答