# 31. Word Search II

Given an `m x n` `board` of characters and a list of strings `words`, return *all words on the board*.

Each word must be constructed from letters of sequentially adjacent cells, where **adjacent cells** are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/11/07/search1.jpg)

```
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:**

![](https://assets.leetcode.com/uploads/2020/11/07/search2.jpg)

```
Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
```

## Solution: (Backtracking)

```cpp
class Solution
{
public:
    bool dfs(vector<vector<char>> &board, int i, int j, string word, int pos)
    {
        int n = board.size();
        int m = board[0].size();

        if (pos == word.length())
        {
            return true;
        }

        if (i >= 0 && j >= 0 && i < n && j < m && word[pos] == board[i][j])
        {
            
            char temp = board[i][j];
            board[i][j] = ' ';

            if (dfs(board, i + 1, j, word, pos + 1))
            {
                 board[i][j] = temp;
                return true;
            }

            if (dfs(board, i, j + 1, word, pos + 1))
            {
                 board[i][j] = temp;
                return true;
            }

            if (dfs(board, i - 1, j, word, pos + 1))
            {
                 board[i][j] = temp;
                return true;
            }

            if (dfs(board, i, j - 1, word, pos + 1))
            {
                 board[i][j] = temp;
                return true;
            }
            
            board[i][j] = temp;
        }

        return false;
    }

    vector<string> findWords(vector<vector<char>> &board, vector<string> &words)
    {
        vector<string> res;

        for (int k = 0; k < words.size(); k++)
        {
            bool flag = false;
            for (int i = 0; i < board.size(); i++)
            {
                for (int j = 0; j < board[i].size(); j++)
                {
                    if (words[k][0] == board[i][j])
                    {
                        if (dfs(board, i, j, words[k], 0))
                        {
                            flag = true;
                            res.push_back(words[k]);
                            break;
                        }
                    }
                }

                if (flag)
                {
                    break;
                }
            }
        }

        return res;
    }
};
```

**Time Complexity: (nm \* nm \* numWords)**

## Solution: (Trie)

```cpp
class Solution
{
public:
    struct TrieNode
    {
        char val;
        int endHere;
        string word;
        TrieNode *child[26];
    };

    TrieNode *createNode(char ch)
    {
        TrieNode *temp = new TrieNode;
        temp->val = ch;
        temp->endHere = 0;
        temp->word = "";
        for (int i = 0; i < 26; i++)
        {
            temp->child[i] = NULL;
        }

        return temp;
    }

    vector<string> res;

    void dfs(vector<vector<char>> &board, TrieNode *root, int i, int j)
    {
        int n = board.size();
        int m = board[0].size();

        if (i < 0 || j < 0 || i >= n || j >= m)
        {
            return;
        }

        if (board[i][j] == '*')
        {
            return;
        }

        int idx = board[i][j] - 97;

        root = root->child[idx];

        if (root == NULL || root->val != board[i][j])
        {
            return;
        }

        if (root->endHere > 0)
        {
            res.push_back(root->word);
            root->endHere--;
        }

        char temp = board[i][j];
        board[i][j] = '*';

        dfs(board, root, i + 1, j);
        dfs(board, root, i - 1, j);
        dfs(board, root, i, j + 1);
        dfs(board, root, i, j - 1);

        board[i][j] = temp;
        return;
    }

    void insert(string word, TrieNode *root)
    {
        TrieNode *p = root;
        for (int i = 0; i < word.length(); i++)
        {
            int node = word[i] - 97;
            if (!p->child[node])
            {
                p->child[node] = createNode(word[i]);
            }
            p = p->child[node];
        }
        p->endHere++;
        p->word = word;
    }

    vector<string> findWords(vector<vector<char>> &board, vector<string> &words)
    {
        TrieNode *root = createNode('/');

        for (int i = 0; i < words.size(); i++)
        {
            insert(words[i], root);
        }

        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                int ch = board[i][j] - 97;
                if (root->child[ch])
                {
                    dfs(board, root, i, j);
                }
            }
        }
        return res;
    }
};
```

**Time Complexity: (nm \* nm)**


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://soumyajit4419.gitbook.io/ds-algo/graph/31.-word-search-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.