Word Search II

We can solve the problem using Trie data structure and Depth First Search (DFS). The idea is to insert all the words into a Trie and then search the words from the given board using DFS.

Here’s the step-by-step guide to solving this problem:

  1. Build a Trie from the given words: A Trie is a tree-like data structure that is used to store a dynamic set of strings, where the keys are usually strings. We’ll insert all the given words into a Trie.

  2. Search the Board: We’ll iterate through every cell in the given board and use DFS to check if the current cell can form any word present in the Trie.

  3. Backtracking: As we do DFS, we’ll use backtracking to explore all possible paths from the current cell.

Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # Function to build a trie from words
        def build_trie():
            trie = {}
            for word in words:
                node = trie
                for ch in word:
                    if ch not in node:
                        node[ch] = {}
                    node = node[ch]
                node['#'] = True
            return trie

        # DFS function to search words from the board
        def dfs(board, trie, i, j, path, ans):
            ch = board[i][j]
            if ch not in trie:
                return
            trie = trie[ch]
            path += ch
            if '#' in trie:
                ans.add(path)
            board[i][j] = '@'
            directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
            for di, dj in directions:
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '@':
                    dfs(board, trie, ni, nj, path, ans)
            board[i][j] = ch

        trie = build_trie()
        m, n = len(board), len(board[0])
        ans = set()
        for i in range(m):
            for j in range(n):
                dfs(board, trie, i, j, "", ans)

        return list(ans)

Here, build_trie function builds the Trie from the given words, and dfs function performs the DFS to find all the words on the board. We use a set ans to store the unique words found, and finally return it as a list.

The code handles the constraints properly and returns all words found on the board, satisfying the given conditions.

Identifying Problem Isomorphism

“Word Search II” has an approximate isomorph: “Boggle”

In “Word Search II”, you’re given a 2D board and a list of words from a dictionary. You’re required to find all words in the board. Each word must be constructed from letters of sequentially adjacent cells, where “adjacent” cells are horizontally or vertically neighboring and the same letter cell may not be used more than once in a word.

Similarly, in “Boggle”, you’re given a 2D grid of letters and a dictionary of words, and you need to find all valid words from the dictionary that can be formed from the letters in the grid. The rules of forming a word are the same as in “Word Search II”.

Both share a very similar structure and require a depth-first search approach along with some form of Trie or prefix search to efficiently check if a string is a word or the prefix of a word.

The difficulty level of both problems is similar as they have the same problem structure and require similar approaches to solve.

10 Prerequisite LeetCode Problems

The “Word Search II” involves the use of Depth-First Search (DFS) and Trie data structure. Here are 10 problems to prepare for it:

  1. “Word Search” (LeetCode Problem #79): This problem is the simpler version where you only need to find one word instead of multiple words.

  2. “Implement Trie (Prefix Tree)” (LeetCode Problem #208): This problem introduces the Trie data structure which is used in “Word Search II” to efficiently search for multiple words.

  3. “Add and Search Word - Data structure design” (LeetCode Problem #211): This problem is a good next step after implementing a Trie. It challenges you to implement a data structure that supports adding and searching words.

  4. “Prefix and Suffix Search” (LeetCode Problem #745): This problem further exercises your understanding of Trie data structures in a more complex context.

  5. “Number of Islands” (LeetCode Problem #200): This problem helps to get comfortable with Depth-First Search on a grid which is a crucial part for “Word Search II”.

  6. “Flood Fill” (LeetCode Problem #733): This is another problem to practice DFS on a grid.

  7. “Longest Word in Dictionary” (LeetCode Problem #720): In this problem, you can practice using Trie to solve real-world problems.

  8. “Replace Words” (LeetCode Problem #648): This problem combines Trie and string manipulation, providing good practice for “Word Search II”.

  9. “Stream of Characters” (LeetCode Problem #1032): This problem uses Trie in a streaming context, providing an interesting twist.

  10. “Maximum XOR of Two Numbers in an Array” (LeetCode Problem #421): This problem will help you to think about how Trie can be used in a bitwise operation context.

These cover DFS and Trie, and get you comfortable with manipulating these data structures.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

from functools import reduce
from collections import defaultdict

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        Trie = lambda: defaultdict(Trie)
        trie = Trie()
        END = True

        for word in words:
            reduce(dict.__getitem__,word,trie)[END] = word

        res = set()
        def findstr(i,j,t):
            if END in t:
                res.add(t[END])

            letter = board[i][j]
            board[i][j] = ""
            if i > 0 and board[i-1][j] in t:
                findstr(i-1,j,t[board[i-1][j]])
            if j>0 and board[i][j-1] in t:
                findstr(i,j-1,t[board[i][j-1]])
            if i < len(board)-1 and board[i+1][j] in t:
                findstr(i+1,j,t[board[i+1][j]])
            if j < len(board[0])-1 and board[i][j+1] in t:
                findstr(i,j+1,t[board[i][j+1]])
            board[i][j] = letter

            return 

        for i, row in enumerate(board):
            for j, char in enumerate(row):
                if board[i][j] in trie:
                    findstr(i,j,trie[board[i][j]])
        return res

Problem Classification

Here is an approach to find all words from a board of characters:

  1. Create a Trie of the words list for efficient lookup.

  2. Do a DFS traversal of the board, exploring each valid path.

  3. At each cell, check if prefix exists in Trie. If a full word is found, add to result.

  4. Mark visited letters to avoid reusing in same word.

  5. Recursively explore neighbors and backtrack.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

class TrieNode:
  def __init__(self):
    self.children = {}
    self.end = False
    
class Trie:

  def __init__(self):
    self.root = TrieNode()

  # Insert word  
  def insert(self, word):
    
    node = self.root
    for c in word:
      if c not in node.children:
        node.children[c] = TrieNode()
      node = node.children[c]
    node.end = True

  # Search prefix
  def search(self, prefix):
    node = self.root
    for c in prefix:
      if c not in node.children:
        return False
      node = node.children[c]
    return True

def findWords(board, words):
  
  trie = Trie()
  for w in words:
    trie.insert(w)
  
  result = []
  m, n = len(board), len(board[0])
  
  visited = set()
  
  def dfs(i, j, node, word):
    
    if node.end:
      result.append(word)
      node.end = False
    
    if i < 0 or i >= m or j < 0 or j >= n or (i, j) in visited or board[i][j] not in node.children:
      return

    visited.add((i, j))  
    node = node.children[board[i][j]]
    word += board[i][j]

    dfs(i+1, j, node, word)  
    dfs(i-1, j, node, word)
    dfs(i, j+1, node, word)
    dfs(i, j-1, node, word)

    visited.remove((i, j))

  for i in range(m):
    for j in range(n):
      dfs(i, j, trie.root, "")
      
  return result

The key is using a Trie for efficient prefix lookup to find words during DFS traversal.

Here is an implementation in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.word = word
        
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        
        trie = Trie()
        for word in words:
            trie.insert(word)
            
        ROWS, COLS = len(board), len(board[0])
        res = []
        visit = set()
        
        def dfs(r, c, node):
            
            if (r < 0 or c < 0 or 
                r == ROWS or c == COLS or
                board[r][c] not in node.children or
                (r, c) in visit):
                return
            
            visit.add((r, c))
            node = node.children[board[r][c]]
            word = node.word
            
            if word:
                res.append(word)
                node.word = None
                
            dfs(r-1, c, node)
            dfs(r+1, c, node) 
            dfs(r, c-1, node)
            dfs(r, c+1, node)
            
            visit.remove((r, c))
            
        for r in range(ROWS):
            for c in range(COLS):
                dfs(r, c, trie.root)
                
        return res

The key steps are:

  • Build a Trie of words
  • DFS traversal of board
  • Check if prefix exists in Trie
  • Backtrack and mark visited
  • Return all matched words

This allows efficiently finding valid words during board traversal.

Language Agnostic Coding Drills

The code provides a solution to the problem of finding all words in a given list that are also in a 2D board. The code leverages a data structure known as Trie (also known as Prefix Tree) for efficient word search, and uses Depth-First Search (DFS) for board traversal.

Let’s break down the code into separate concepts:

  1. Understanding the problem and data structures used: Understand how a 2D board is represented in programming and how a list of words can be searched. Also understand what a Trie data structure is and how it is used for efficient word search.

  2. Use of defaultdict and lambda functions: Understand the use of Python’s defaultdict and lambda functions. Practice using these tools in different contexts, and understand how they are used here to create a Trie.

  3. Understanding of recursion and depth-first search (DFS): The findstr function is a recursive function that performs DFS on the board. Understanding how DFS works, especially in the context of a 2D grid, is essential to understand this code.

  4. String manipulation: Understand how strings are created, accessed, and modified in Python. The reduce function is used here to traverse the Trie, which requires an understanding of string manipulation.

  5. Use of Enumerate in loops: The code uses enumerate in for loops to get both the index and the value of the elements. Understanding how enumerate works and when to use it would be beneficial.

  6. Understanding Ternary Operations: The statement [END] = word is a Pythonic way to add a word to a Trie. Understanding this type of operation will help to understand this code.

  7. Working with sets: The result is stored in a set, which automatically removes duplicates. Understanding how to work with sets, including adding elements and converting sets to lists, is another crucial part of understanding this code.

  8. Nested function and variable scope: The function findstr is defined inside the main function, and it uses variables that are defined in the outer function. Understanding how nested functions and variable scope work in Python is necessary to understand this code.

By mastering each of these smaller units of learning separately, one can combine these skills to understand the given solution. Each of these drills can be made language agnostic by focusing on the concepts (data structures, recursion, string manipulation, etc.) rather than the specific Python syntax. The final solution applies the Trie data structure for efficient word search, and uses DFS for board traversal, demonstrating a common strategy for solving complex problems in computer science: using the right data structures and algorithms for the task.

Targeted Drills in Python

  1. Understanding the problem and data structures used: Drill: Create a 2D board and a list of words. Write a function to check if a word is present in the board.

    1
2
3
4
5
6
7
8
9

    board = [
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
]
words = ["ABCCED", "SEE", "ABCB"]

def is_word_in_board(board, word):
    # Implementation left as an exercise

  2. Use of defaultdict and lambda functions: Drill: Use defaultdict and lambda to create a dictionary with default values as empty lists.

    1
2

    from collections import defaultdict
d = defaultdict(lambda: [])

  3. Understanding of recursion and depth-first search (DFS): Drill: Implement a DFS to traverse a binary tree.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

    class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def dfs(node):
    if node is None:
        return
    print(node.val)
    dfs(node.left)
    dfs(node.right)

  4. String manipulation: Drill: Write a function that reverses a string.

    1
2

    def reverse_string(s):
    return s[::-1]

  5. Use of Enumerate in loops: Drill: Given a list, print each element and its index using enumerate.

    1
2
3

    l = ['a', 'b', 'c', 'd', 'e']
for i, el in enumerate(l):
    print(f"Index: {i}, Element: {el}")

  6. Understanding Ternary Operations: Drill: Write a function that returns the maximum of two numbers using ternary operations.

    1
2

    def max(a, b):
    return a if a > b else b

  7. Working with sets: Drill: Create a set, add elements to it, remove duplicates from a list using a set.

    1
2
3
4
5
6
7
8
9

    s = set()
s.add(1)
s.add(2)
s.add(1)
print(s)

l = [1, 2, 3, 2, 1]
l = list(set(l))
print(l)

  8. Nested function and variable scope: Drill: Write a function that has a nested function inside it. The nested function should modify a variable in the outer function’s scope.

    1
2
3
4
5
6
7

    def outer():
    x = 1
    def inner():
        nonlocal x
        x += 1
    inner()
    print(x)

Once you’ve worked through these drills, you should be equipped with the skills necessary to understand the problem and its solution. Try to combine these drills to solve the problem.