Vultr DocsLatest Content

Word Search II

Updated on 03 July, 2025
Word Search II header image

Problem Statement

In this task, you are presented with a grid (or board) of lower-case English letters measuring m x n in size, and a list titled words containing strings. The goal is to identify and return all strings from the words list that can be constructed by tracing a path through adjacent cells on the board. Adjacent cells include those directly above, below, to the left, or to the right of a cell, but not diagonally adjacent. Important to note, each cell in the board can only be used once for constructing each word. This constraint adds a layer of complexity as one cannot simply reuse a heavily surrounded cell to form multiple parts of a word.

Examples

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:

[]

Constraints

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 12
  • board[i][j] is a lowercase English letter.
  • 1 <= words.length <= 3 * 104
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.
  • All the strings of words are unique.

Approach and Intuition

Algorithm Overview

The ideal approach can be conceptualized through employing either Depth-First Search (DFS) or a Trie (prefix tree):

  1. Build a Trie:

    • Initially, construct a Trie structure from all the words. This process helps in search optimization by keeping track of all possible character sequences without redundant processing.

  2. DFS Traversal:

    • Start from each cell in the board and use DFS to try constructing words. When moving to any adjacent cell:
      • Verify if the current string of characters corresponds to any prefix or full word in the Trie.
      • If it matches a word in the Trie, add it to the result set.
      • Continue the DFS for each adjacent cell.

  3. Backtracking:

    • As one moves deeper into the board, mark cells as visited to prevent reuse in constructing the current word attempt. After returning from a recursive DFS call, unmark this cell (backtrack) to enable its use for other potential word constructions.

Example Breakdown

Let's consider the first example:

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

  • Search Mechanism:

    • Starting at any 'o' on the board, we take all possible paths like 'oa', 'oe', etc. Using the constructed Trie, only continue paths that match prefixes stored in the Trie.
    • Word 'oath' fits the Trie and available paths, and is found and added to the output list.

This efficient combination of Trie and DFS enables a systematic exploration of potential words while immediately pruning paths that cannot form valid words in the list, thereby optimizing the search especially when considering the constraints where m and n can be as large as 12, and total word counts significantly high.

Solutions

  • C++
cpp 
class Trie {
public:
    unordered_map<char, Trie*> map;
    string endOfWord;
    
    Trie() : endOfWord("") {}
};
    
class Solution {
private:
    vector<vector<char>> gameBoard;
    vector<string> foundWords;
    
public:
    vector<string> searchWords(vector<vector<char>>& board,
                               vector<string>& words) {
        Trie* root = new Trie();
        for (string& word : words) {
            Trie* node = root;
            for (char ch : word) {
                if (node->map.find(ch) != node->map.end()) {
                    node = node->map[ch];
                } else {
                    Trie* newNode = new Trie();
                    node->map[ch] = newNode;
                    node = newNode;
                }
            }
            node->endOfWord = word;
        }
    
        this->gameBoard = board;
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                if (root->map.find(board[i][j]) != root->map.end()) {
                    explore(i, j, root);
                }
            }
        }
    
        return this->foundWords;
    }
    
private:
    void explore(int i, int j, Trie* root) {
        char letter = this->gameBoard[i][j];
        Trie* currentNode = root->map[letter];
    
        if (currentNode->endOfWord != "") {
            this->foundWords.push_back(currentNode->endOfWord);
            currentNode->endOfWord = "";
        }
    
        this->gameBoard[i][j] = '#';
    
        int dRow[] = {-1, 0, 1, 0};
        int dCol[] = {0, 1, 0, -1};
        for (int d = 0; d < 4; ++d) {
            int ni = i + dRow[d];
            int nj = j + dCol[d];
            if (ni < 0 || ni >= this->gameBoard.size() || nj < 0 ||
                nj >= this->gameBoard[0].size()) {
                continue;
            }
            if (currentNode->map.find(this->gameBoard[ni][nj]) !=
                currentNode->map.end()) {
                explore(ni, nj, currentNode);
            }
        }
    
        this->gameBoard[i][j] = letter;
    
        if (currentNode->map.empty()) {
            root->map.erase(letter);
        }
    }
};

The provided C++ solution for the problem involves finding a set of words on a given game board using a Trie and backtracking technique.

  • The program starts by implementing a Trie data structure with methods to add words into this Trie. Each Trie node contains a map linking each character to the next Trie node and a string to mark the end of a word.

  • The searchWords function initializes the Trie with each word from the input list. This setup helps in efficient word prefix matching, which is critical for searching in a matrix.

  • The main logic for searching words in the board is implemented in the explore function. This function uses Depth First Search (DFS) recursively to traverse the game board. Each traversed character on the board corresponds to a path in the Trie. If a complete word is found, it is added to the result list.

  • The search avoids revisiting by marking the visited board cell with a special character (#). After all possible routes are explored from a cell, it is reset to its original character. This ensures that the algorithm can revisit the cell for different potential words.

  • Optimization is evident in managing Trie nodes. If a node has no children (meaning no further paths can lead to a word), it is cleaned up from memory, improving performance and reducing resource usage.

Overall, the solution efficiently searches for multiple words on a board by leveraging Trie for quick prefix searches and optimizations in backtracking to manage memory and processing time effectively.

  • Java
java 
class TrieNode {
    HashMap<Character, TrieNode> map = new HashMap<>();
    String terminalWord = null;
    
    public TrieNode() {}
}
    
class WordSearch {
    char[][] gameBoard = null;
    ArrayList<String> foundWords = new ArrayList<>();
    
    public List<String> search(char[][] board, String[] dictionary) {
        TrieNode root = new TrieNode();
        for (String word : dictionary) {
            TrieNode currentNode = root;
    
            for (char letter : word.toCharArray()) {
                currentNode = currentNode.map.computeIfAbsent(letter, k -> new TrieNode());
            }
            currentNode.terminalWord = word;
        }
    
        this.gameBoard = board;
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[r].length; c++) {
                if (root.map.containsKey(board[r][c])) {
                    explore(r, c, root);
                }
            }
        }
    
        return this.foundWords;
    }
    
    private void explore(int row, int col, TrieNode parent) {
        char letter = gameBoard[row][col];
        TrieNode node = parent.map.get(letter);
    
        if (node.terminalWord != null) {
            foundWords.add(node.terminalWord);
            node.terminalWord = null;
        }
    
        gameBoard[row][col] = '#';
    
        int[] dRow = {-1, 0, 1, 0};
        int[] dCol = {0, 1, 0, -1};
        for (int i = 0; i < 4; i++) {
            int newRow = row + dRow[i];
            int newCol = col + dCol[i];
            if (
                newRow >= 0 &&
                newCol >= 0 &&
                newRow < gameBoard.length &&
                newCol < gameBoard[0].length &&
                node.map.containsKey(gameBoard[newRow][newCol])
            ) {
                explore(newRow, newCol, node);
            }
        }
    
        gameBoard[row][col] = letter;
    
        if (node.map.isEmpty()) {
            parent.map.remove(letter);
        }
    }
}

This Java solution utilizes a Trie structure for optimizing the search of words on a board. The board is represented as a 2D character array, and the dictionary of words to be searched is provided as an array of strings.

The core class TrieNode hosts a hash map to track child nodes and an optional terminal string indicating the completion of a word at that node. The WordSearch class contains the primary logic for the word search on the board using the trie:

  • Initialization: Populate the trie with words from the dictionary. Each character of a word is mapped through the trie nodes using a hash map.

  • Board Traversal: For each cell on the board, begin a search if its character exists in the trie. This leverages the explore function for a depth-first search (DFS).

  • DFS Mechanism (explore function): Recursively explore from one cell in all four possible directions (up, down, left, right). If the end of a word is found, it is added to the result list. To prevent revisiting cells, the current cell is temporarily marked. After completion of a path, unmark the cell and adjust the trie to remove completed words for memory efficiency.

  • Bounds and Existence Checks: Ensure movements stay within bounds and lead to existing trie nodes to continue the search effectively.

Useful for implementing efficient word search tools where rapid validation against a dictionary is required (e.g., word game bots). This approach minimizes unnecessary searches and checks, making it both time and memory efficient.

  • Python
python 
class Solution:
    def searchWords(self, grid: List[List[str]], dictionary: List[str]) -> List[str]:
        end_symbol = "#"
    
        prefix_tree = {}
        for item in dictionary:
            node = prefix_tree
            for char in item:
                node = node.setdefault(char, {})
            node[end_symbol] = item
    
        max_rows = len(grid)
        max_cols = len(grid[0])
    
        result = []
    
        def dfs(r, c, node):
    
            char = grid[r][c]
            current_node = node[char]
    
            match = current_node.pop(end_symbol, False)
            if match:
                result.append(match)
    
            grid[r][c] = "@"
    
            for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                new_r, new_c = r + dr, c + dc
                if new_r < 0 or new_r >= max_rows or new_c < 0 or new_c >= max_cols:
                    continue
                if not grid[new_r][new_c] in current_node:
                    continue
                dfs(new_r, new_c, current_node)
    
            grid[r][c] = char
    
            if not current_node:
                node.pop(char)
    
        for r in range(max_rows):
            for c in range(max_cols):
                if grid[r][c] in prefix_tree:
                    dfs(r, c, prefix_tree)
    
        return result

This Python3 solution involves finding all words from a given dictionary that can be formed by traversing a grid of characters. The process employs a depth-first search (DFS) strategy integrated with a Trie (prefix tree) data structure to efficiently manage and search through the dictionary.

  • Start by creating a Trie, where each node represents a possible character in the dictionary words. This helps in quick look-up and ensures that only dictionary words are considered during the search.
  • Initialize the grid dimensions and a result list to store the valid words found.
  • Define the dfs function, which will be used to explore the grid. For every character that matches with the Trie, recursively explore in all four possible directions (up, right, down, left).
  • To prevent revisiting the same cell, replace the character at grid[r][c] with a special character (in this case, "@") during the DFS traversal and reset it back once all possible paths from that cell are explored.
  • If a word is found (by reaching a node in the Trie that has the end_symbol indicating the end of a valid word), add it to the result list.
  • Optimize the Trie by removing nodes that are no longer needed, reducing the memory footprint as exploration progresses.
  • The search is initiated from every cell in the grid that matches the starting character of any prefix in the Trie.

The approach ensures that all possible word combinations are explored and that the search space is pruned using the Trie structure to avoid unnecessary computations for sequences that do not lead to a valid dictionary word. The solution is comprehensive and manages both the search process and Trie traversal efficiently, making it suitable for larger grids and dictionaries.

Comments

No comments yet.