> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/graph/31.-word-search-ii.md).

# 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)**