Python: Find A Word In A Matrix Of Characters
I am trying to create a word game that involves finding words in a matrix of 5x5 characters, like so: [['a', 'a', 'u', 'r', 'a'], ['m', 'v', 'g', 'n', 'x'], ['a', 'q', 'h', 'y',
Solution 1:
If you want to check for word membership, your starting point of a dictionary mapping letters to positions is a good one:
letter_positions = {}
for (y, row) in enumerate(board):
for (x, letter) in enumerate(row):
letter_positions.setdefault(letter, []).append((x, y))
From there, your function should keep track of which letters have already been used to make sure it doesn't duplicate them:
defmove_valid(position, last_position):
if last_position isNone:
returnTruereturn (
abs(position[0] - last_position[0]) <= 1andabs(position[1] - last_position[1]) <= 1
)
deffind_word(word, used=None):
if word == "":
return []
if used isNone:
used = []
letter, rest = word[:1], word[1:]
for position in letter_positions.get(letter) or []:
if position in used:
continueifnot move_valid(position, used and used[-1]):
continue
path = find_word(rest, used + [position])
if path isnotNone:
return [position] + path
returnNone
And for example:
>>>find_word("xylon")
[(4, 1), (3, 2), (3, 3), (4, 2), (3, 1)]
>>>find_word("bad")
None
Now, note that the runtime here will be O(not great)
because of the position in used
(used
is a list and will require an O(N)
search for each letter position) and the used + [position]
and [position] + path
(each of which will result in an allocation + copy). In practice this will be ~O(word length ^ 2)
, but could be improved to ~O(word length)
with some more sensible data structures.
Post a Comment for "Python: Find A Word In A Matrix Of Characters"