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.