[Solution]Problem 18: Pack Words on Board [Google]
Recursion, Words, Matrix,
Following is a solution shared with the subscribers of the newsletter. To gain access to more such solutions and join programmers/software developers acing their coding and system design interviews, become a premium subscriber of the newsletter here:
Problem
This problem was asked by Google.
You are given an N by M matrix of random letters and a dictionary of words. Find the maximum number of words that can be packed on the board from the given dictionary.
A word is considered to be able to be packed on the board if:
It can be found in the dictionary
It can be constructed from untaken letters by other words found so far on the board
The letters are adjacent to each other (vertically and horizontally, not diagonally).
Each tile can be visited only once by any word.
For example, given the following dictionary:
{ 'eat', 'rain', 'in', 'rat' }
and matrix:
[['e', 'a', 'n'],
['t', 't', 'i'],
['a', 'r', 'a']]
Your function should return 3, since we can make the words 'eat', 'in', and 'rat' without them touching each other. We could have alternatively made 'eat' and 'rain', but that would be incorrect since that's only 2 words.
Step 1: Identifying a methodology
We have been given a problem where we have multiple possible valid configurations. There are a few conditions, and we want a configuration that maximizes a certain objective (in this case length of the list). This should start ringing a few bells in your head. When we run into such conditions, we know that backtracking will lead to a solution.
Step 2: Backtracking
To those of you not familiar with backtracking, it is an algorithmic technique for solving problems recursively. We try to build a solution incrementally, one piece at a time. We remove solutions that fail to satisfy the constraints of the problem at any point in time. If you’re familiar with Evolutionary Algorithms, it is a similar principle.
So what do we need to consider? First off, we are going through and picking letters. The next state of the solution depends on the letter you pick now. And your final configuration can only be figured out by going through every option. This means that we want to use Depth First Search (DFS). Following is a good animation of DFS for finding cycles.
Finding Directions
The next step to figure out is how we are traversing through the matrix to find our words. Remember that we can only pick adjacent words. And diagonals are not considered adjacent. Therefore if our letter was at (x,y) we can pick from indexes [(x-1,y), (x+1, y), (x, y-1), (x, y+1)]. We represent the directions in our code using
DIRECTIONS = [
(1, 0),
(-1, 0),
(0, 1),
(0, -1),
] Building our Max Words Function
To build up our recursive solution, we want to keep track of a few different things. We obviously need our board and its dimensions alongside the allowed words. We also need to track which indexes we visited (to not repeat values), and the current word we have formed. And once we form a word, we’ll add it to our word list, so we track that as well. And naturally, we need the current row and column index we’re in.
def max_words(board, n, m, words, visited, r, c, curr_word):We also want to save time by terminating whenever we can. There are two invalid conditions: 1) When we go out of bounds/to already visited words which we check by doing this:
if r < 0 or r >= n or c < 0 or c >= m or visited[r][c]:
return []
and 2) We know that we hit invalid configurations when no words in our words dictionary start with our current word. We code this as:
if not any(word.startswith(curr_word) for word in words):
return [] #this gives our config a score of 0Next, we have 2 possible conditions:
The current word we’re at exists in the dictionary. In this case, we add this to our list and start looking for new words. Since we only care about having many words and not longer words, we should do this.
We haven’t formed a word yet. This implies we have a root of a valid word. So we keep building, till we find the word we’re looking for (or hit termination conditions).
These cases are represented by:
if curr_word in words:
# A valid words has been found: terminate current word search and start a new one
for r, row in enumerate(board):
for c, val in enumerate(row):
curr_word_set = max_words(board, n, m, words, visited, r, c, '')
if len(curr_word_set) > len(max_word_set):
max_word_set = curr_word_set
max_word_set.append(curr_word)
else:
for dr, dc in DIRECTIONS:
curr_word_set = max_words(board, n, m, words, visited, r + dr, c + dc, curr_word)
if len(curr_word_set) > len(max_word_set):
max_word_set = curr_word_setPutting it all together
Now we must put it all together. This is where practice and programming experience helps. Take note of how we integrate the constraints, and how we initialize the values. Notice how we work in the building blocks we developed individually. All of this comes by practicing lots of problems.
For an intelligent plan that you can use to ace your interviews check out this article. This contains proven steps that students have used to ace their interviews.
Our final solution looks like
DIRECTIONS = [
(1, 0),
(-1, 0),
(0, 1),
(0, -1),
]
def max_words(board, n, m, words, visited, r, c, curr_word):
if r < 0 or r >= n or c < 0 or c >= m or visited[r][c]:
return []
curr_word += board[r][c]
# if no words in |words| start with |curr_word|, then return early.
if not any(word.startswith(curr_word) for word in words):
return []
visited[r][c] = True
max_word_set = []
if curr_word in words:
# A valid words has been found: terminate current word search and start a new one
for r, row in enumerate(board):
for c, val in enumerate(row):
curr_word_set = max_words(board, n, m, words, visited, r, c, '')
if len(curr_word_set) > len(max_word_set):
max_word_set = curr_word_set
max_word_set.append(curr_word)
else:
for dr, dc in DIRECTIONS:
curr_word_set = max_words(board, n, m, words, visited, r + dr, c + dc, curr_word)
if len(curr_word_set) > len(max_word_set):
max_word_set = curr_word_set
visited[r][c] = False
return max_word_set
def find_max_words(board, words):
if not board:
return 0
n, m = len(board), len(board[0])
visited = [[False for _ in range(m)] for _ in range(n)]
max_words_so_far = []
for r, row in enumerate(board):
for c, val in enumerate(row):
word_set = max_words(board, n, m, words, visited, r, c, '')
if len(word_set) > len(max_words_so_far):
max_words_so_far = word_set
print(max_words_so_far)
return len(max_words_so_far)Since this solution goes down all the different paths, the runtime is exponential.
Final: Exponential Time
Bonuses/Promotion (Get Free Stuff)
Have anything to say to me? Use the links below.
To learn how to interview better DM me. Let’s set up mock interviews and go over different interview techniques. In addition to focused questions, and a detailed personalized plan, we will go over the right questions to ask during your interviews.
For most of my students, mock interviews have been very helpful. Enough mock interview practice is the key between getting that job offer and rejection. If you can get three people to become paying subscribers to this newsletter, you win a free mock interview. This offer has no upper limit, so the more subs you can get, the more mock interviews you win.
To share interesting problems/solutions with me, reach out to me. Different social media of mine also have other content from me. Good problems and/or solutions receive a free shoutout + 2 months of the paid newsletter:
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75