Word Search II Leetcode Problem 212 [Python Solution]

Today, we’ll tackle the Word Search II Question , a challenging task categorized under “Hard” in LeetCode’s Blind 75 list.

This problem extends from “Word Search I” (LeetCode 79), so it’s crucial to understand the basics before diving into this one.

The problem revolves around an m x n board of characters and a list of strings (words).

Our goal is to identify which words from the list can be constructed using letters from the board.

The catch is that each letter on the board can only be used once in a word, and the word can be formed by adjacent (horizontally or vertically) cells on the board.

Let’s get started by understanding the problem in detail.

Problem Overview

Given an m x n board of characters and a list of strings, we must return all the words that can be formed on the board.

Example 1:

Input:

board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
words = ["oath","pea","eat","rain"]

Output:

["eat","oath"]

Example 2:

Input:

board = [["a","b"],["c","d"]]
words = ["abcb"]

Output:

[]

Understanding the Constraints

Before we dive into the solution, it’s crucial to understand the constraints:

• m is the number of rows in the board.
• n is the number of columns in the board.
• The board consists of lowercase English letters.
• The list of words has a length ranging from 1 to 30,000.
• Each word in the list consists of lowercase English letters and is unique.

Word Search II LeetCode Problem Solution

We’ll solve this problem using a combination of depth-first search (DFS) and a Trie data structure.

The Trie will help us efficiently organize and search for words based on their prefixes.

1. TrieNode Class

To implement the Trie, we’ll start by defining a TrieNode class.

This class will have the following attributes:

• children: A dictionary where each key is a character, and the corresponding value is a TrieNode representing the next character.
• isWord: A boolean flag indicating whether the current node marks the end of a word.
• refs: An integer to keep track of the number of references to a particular node.

We’ll also implement methods for adding and removing words from the Trie.

Here’s the Python code for the TrieNode class:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False
        self.refs = 0

    def addWord(self, word):
        cur = self
        cur.refs += 1
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
            cur.refs += 1
        cur.isWord = True

    def removeWord(self, word):
        cur = self
        cur.refs -= 1
        for c in word:
            if c in cur.children:
                cur = cur.children[c]
                cur.refs -= 1

2. Full Efficient Python Code Solution

Now, let’s delve into the efficient solution for the Word Search II problem.

We’ll use a Trie to store the words from the list and a depth-first search (DFS) to traverse the board.

The idea is to simultaneously check all words that can be created starting from each position on the board.

We’ll maintain a Trie to organize words based on their prefixes, and as we traverse the board, we’ll check the Trie for potential words.

Here’s the Python code for the efficient solution:

class TrieNode:<br>    def __init__(self):<br>        self.children = {}<br>        self.isWord = False<br>        self.refs = 0<br><br>    def addWord(self, word):<br>        cur = self<br>        cur.refs += 1<br>        for c in word:<br>            if c not in cur.children:<br>                cur.children[c] = TrieNode()<br>            cur = cur.children[c]<br>            cur.refs += 1<br>        cur.isWord = True<br><br>    def removeWord(self, word):<br>        cur = self<br>        cur.refs -= 1<br>        for c in word:<br>            if c in cur.children:<br>                cur = cur.children[c]<br>                cur.refs -= 1<br><br>class Solution:<br>    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:<br>        root = TrieNode()<br><br>        # Add all words to the Trie<br>        for w in words:<br>            root.addWord(w)<br><br>        ROWS, COLS = len(board), len(board[0])<br>        result, visit = set(), set()<br><br>        def dfs(r, c, node, word):<br>            if (<br>                r not in range(ROWS) <br>                or c not in range(COLS)<br>                or board[r][c] not in node.children<br>                or node.children[board[r][c]].refs &lt; 1<br>                or (r, c) in visit<br>            ):<br>                return<br><br>            visit.add((r, c))<br>            node = node.children[board[r][c]]<br>            word += board[r][c]<br><br>            if node.isWord:<br>                node.isWord = False<br>                result.add(word)<br>                root.removeWord(word)<br><br>            dfs(r + 1, c, node, word)<br>            dfs(r - 1, c, node, word)<br>            dfs(r, c + 1, node, word)<br>            dfs(r, c - 1, node, word)<br>            visit.remove((r, c))<br><br>        for r in range(ROWS):<br>            for c in range(COLS):<br>                dfs(r, c, root, "")<br><br>        return list(result)<br>

Time and Space Complexity

The time complexity of this solution depends on the number of words in the list (w), the size of the board (m x n), and the average length of words (k).

In the worst case, we’ll perform a DFS starting from each position on the board, resulting in a time complexity of O(w * m * n * 4^k).

The space complexity mainly depends on the Trie structure, which uses space proportional to the sum of the lengths of all words in the list, making it O(w * k).

Reasoning Behind Our Approach

Our approach optimizes the search process by using a Trie data structure to organize words based on their prefixes.

This allows us to efficiently search for words that could be created starting from a specific position on the board.

The use of depth-first search (DFS) helps us traverse the board and check for potential words, eliminating the need to search for the same word multiple times.

Related Interview Questions By Company:

• Find Critical And Pseudo Critical Edges In Minimum Spanning Tree
• Word Ladder LeetCode
• N Queens II LeetCode

Related Interview Questions By Difficulty:

• Design Add And Search Words Data Structure LeetCode
• Word Search II LeetCode

Conclusion

In this blog post, we’ve tackled the Word Search II problem on LeetCode.

We’ve developed an efficient solution that leverages Trie data structures and depth-first search.

By organizing words based on their prefixes, we can efficiently determine which words can be constructed on the board.

If you found this post helpful, please consider liking and subscribing to support our our platform.

Feel free to comment, ask questions, make suggestions, and share the content.

Happy coding!