Python program for Word Search II

Question

This is a Leetcode problem -

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of a sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Note:

• All inputs are consist of lowercase letters a-z.
• The values of words are distinct.

Here is my solution to this challenge -

class Solution:
 def __init__(self, board, words):
 self.board = board
 self.words = words
 def find_words(self, board, words):
 root = {}
 for word in words:
 node = root
 for c in word:
 node = node.setdefault(c, {})
 node[None] = True
 board = {i + 1j * j: c
 for i, row in enumerate(board)
 for j, c in enumerate(row)}
 found = []
 def search(node, z, word):
 if node.pop(None, None):
 found.append(word)
 c = board.get(z)
 if c in node:
 board[z] = None
 for k in range(4):
 search(node[c], z + 1j ** k, word + c)
 board[z] = c
 for z in board:
 search(root, z, '')
 return found

Program explanation - I first build a tree of words with root root and also represent the board a different way, namely as a one-dimensional dictionary where the keys are complex numbers representing the row/column indexes. That makes further work with it easier. Looping over all board positions is just for z in board, the four neighbors of a board position z are just z + 1j ** k (for k in 0 to 3), and I don't need to check borders because board.get just returns None if I request an invalid position.

After this preparation, I just take the tree and recursively dive with it into each board position. Similar to how you'd search a single word, but with the tree instead.

Here is an example input/output -

output = Solution([
 ['o','a','a','n'],
 ['e','t','a','e'],
 ['i','h','k','r'],
 ['i','f','l','v']
], ["oath","pea","eat","rain"])
print(output.find_words([
 ['o','a','a','n'],
 ['e','t','a','e'],
 ['i','h','k','r'],
 ['i','f','l','v']
], ["oath","pea","eat","rain"]))
>>> ['oath', 'eat']

So, I would like to know whether I could make this program shorter and more efficient.

Any help would be highly appreciated.

Answer 1

Awkward API

It seems strange to initialise a Solution object with various info that we provide again in the call of the method find_words.

Actually, looking for places where self is used makes it pretty obvious: the instance is never used.

It is a good occasion to watch the Stop Writing Classes talk from Jack Diederich.

To be continued ?