Word Search II

This question is a follow up from my previous post (Word Search) that was asked in Airbnb.

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 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.

For example,
Given words = ["oath","pea","eat","rain"] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"].

Note:
You may assume that all inputs are consist of lowercase letters a-z.

My Solution

Unlike previous question, this has to be optimized to accommodate large test cases as we currently have list of words instead of just one word (see my previous post). This can be done by immediately stop the backtrack if current candidate doesn’t exist in all words prefix. The idea is to build up the prefix of all words using trie, and limit our scope of search in a trie to speedup the computation. And again do DFS to search all possible paths/strings and append to the result. During the traversal, if we reach the leaf of a node, it means we have found a path, add it to the result but keep going as other words might also contain this word as their prefixes. Return if a letter doesn’t exist in the trie at all.

def word_search(board, words):
  if not board or not words:
    return None
  # build up the prefix trie
  trie = {}
  for w in words:
    t = trie
    for c in w:
      if c not in trie:
        t[c] = {}
      t = t[c]
    t["#"] = "#"  # mark the leaf node
  
  res = []
  for i in range(len(board)):
    for j in range(len(board[0])):
      dfs_helper(board, i, j, trie, '', res)
  return list(set(res))  # a word might have more than one path, use set to remove duplicates

def dfs_helper(board, i, j, trie, path, res):
  # we found leaf node, do not return here but keep going
  if "#" in trie:
    res.append(path)  # add to res array, remember in python array is referred by reference, not value like Java
  
  if i<0 or j<0 or i>=len(board) or j>=len(board[0]) or board[i][j] not in trie:
    return
  tmp = board[i][j]  # first letter found
  board[i][j] = "@"  # mark visited

  res = dfs_helper(board, i-1, j, trie[tmp], path+tmp, res) or \
        dfs_helper(board, i+1, j, trie[tmp], path+tmp, res) or \
        dfs_helper(board, i, j-1, trie[tmp], path+tmp, res) or \
        dfs_helper(board, i, j+1, trie[tmp], path_tmp, res)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s