Find all words placed on a Scrabble board

Any idea whats a simple and fast way to get all words placed on a Scrabble board while the board is represented by 2D Array of chars?

Thanks in a开发者_开发百科dvance

This is similar to Artsiom's answer, but covers for the fact that a Scrabble board will have spaces in between words.

So assuming your "2D Array of chars" looks like this:

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',' ',' ',' ']]

You can do the following:

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]

Which gives:

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

What we're doing is converting each row and column of characters in to strings like 'not mat' and then using str.split() to throw away the spaces to give us a list of words, throwing away anything that's one letter long.

Using itertools.chain() just allows us to loop through the rows and columns in a single list comprehension.

Search top to bottom in each column for contiguous sets of characters then search left to right in each row for the same. Its going to be O(n^2) but I don't think you'll be able to get much better.

If i am correctly understood you than you can also try to use something like this:

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)