Last updated on July 15th, 2024 at 03:30 am

Here, We see ** Word Search II LeetCode Solution**. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

*List of all LeetCode Solution*

*List of all LeetCode Solution*

## Topics

Backtracking, Tree

## Companies

Airbnb, Google, Microsoft

## Level of Question

Hard

**Word Search II LeetCode Solution**

## Table of Contents

**Problem Statement**

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:(fig-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:(fig-2)Input: board = [["a","b"],["c","d"]], words = ["abcb"]Output: []

**1. Word Search II Leetcode Solution C++**

class Solution { struct TrieNode { TrieNode *children[26]; string word; TrieNode() : word("") { for (int i = 0; i < 26; i++) { children[i] = nullptr; } } }; public: vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { TrieNode *root = buildTrie(words); vector<string> result; for (int i = 0; i < board.size(); i++) { for (int j = 0; j < board[0].size(); j++) { dfs(board, i, j, root, result); } } return result; } TrieNode *buildTrie(vector<string> &words) { TrieNode *root = new TrieNode(); for (int j = 0; j < words.size(); j++) { string word = words[j]; TrieNode *curr = root; for (int i = 0; i < word.length(); i++) { char c = word[i] - 'a'; if (curr->children[c] == nullptr) { curr->children[c] = new TrieNode(); } curr = curr->children[c]; } curr->word = word; } return root; } void dfs(vector<vector<char>> &board, int i, int j, TrieNode *p, vector<string> &result) { char c = board[i][j]; if (c == '#' || !p->children[c - 'a']) return; p = p->children[c - 'a']; if (p->word.size() > 0) { result.push_back(p->word); p->word = ""; } board[i][j] = '#'; if (i > 0) dfs(board, i - 1, j, p, result); if (j > 0) dfs(board, i, j - 1, p, result); if (i < board.size() - 1) dfs(board, i + 1, j, p, result); if (j < board[0].size() - 1) dfs(board, i, j + 1, p, result); board[i][j] = c; } };

#### 1.1 Explanation

**TrieNode Structure**:**TrieNode**is a nested structure within**Solution**that holds an array**children**of TrieNode pointers, one for each possible lowercase English letter (‘a’ to ‘z’). Each node also stores a**word**which is the word ending at that node.

**Building the Trie (buildTrie)**:- This function constructs a Trie from a list of words. For each word, it starts at the root and traverses down, creating new nodes as necessary for each character in the word. The final node of each word (
**curr->word**) is marked with the word itself.

- This function constructs a Trie from a list of words. For each word, it starts at the root and traverses down, creating new nodes as necessary for each character in the word. The final node of each word (
**Depth-First Search (dfs)**:- This function explores the board starting from each cell. It checks if the current character exists as a child in the Trie (
**p->children[c – ‘a’]**). If not, or if the character has already been visited (**‘#’**), it returns. - If a word ends at the current node (
**!p->word.empty()**), it adds that word to the result vector (**result**) and clears the word to prevent duplicate results. - It marks the current board cell as visited (
**board[i][j] = ‘#’**), explores neighboring cells recursively (up, down, left, right), and then restores the original character after exploration (**board[i][j] = c**).

- This function explores the board starting from each cell. It checks if the current character exists as a child in the Trie (

#### 1.2 Time Complexity

:**Trie Construction****O(L)**where L is the total length of all words combined.:**DFS Traversal****O(m * n * 4**, where m is the number of rows, n is the number of columns in the board, and L is the maximum length of words.^{L})

#### 1.3 Space Complexity

**Trie Structure**:**O(26 * L * N)**, where L is the average length of words and N is the number of words. Each TrieNode has 26 children pointers and may store up to L characters.**DFS Stack**:**O(m * n)**for recursion depth.

**2. Word Search II Leetcode Solution Java**

class Solution { public List<String> findWords(char[][] board, String[] words) { List<String> res = new ArrayList<>(); TrieNode root = buildTrie(words); for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { dfs (board, i, j, root, res); } } return res; } public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) { char c = board[i][j]; if (c == '#' || p.next[c - 'a'] == null) return; p = p.next[c - 'a']; if (p.word != null) { // found one res.add(p.word); p.word = null; // de-duplicate } board[i][j] = '#'; if (i > 0) dfs(board, i - 1, j ,p, res); if (j > 0) dfs(board, i, j - 1, p, res); if (i < board.length - 1) dfs(board, i + 1, j, p, res); if (j < board[0].length - 1) dfs(board, i, j + 1, p, res); board[i][j] = c; } public TrieNode buildTrie(String[] words) { TrieNode root = new TrieNode(); for (String w : words) { TrieNode p = root; for (char c : w.toCharArray()) { int i = c - 'a'; if (p.next[i] == null) p.next[i] = new TrieNode(); p = p.next[i]; } p.word = w; } return root; } class TrieNode { TrieNode[] next = new TrieNode[26]; String word; } }

#### 2.1 Explanation

**TrieNode Class**:**TrieNode**class represents each node in the Trie. It has an array**next**of size 26 (for ‘a’ to ‘z’) to store child nodes and a**word**string to store the word ending at that node.

**buildTrie Method**:**buildTrie**constructs the Trie from the array of words. It iterates through each word, and for each character in the word, it checks if the corresponding child node exists. If not, it creates a new**TrieNode**and moves to that node.

**dfs Method**:**dfs**(Depth-First Search) is used to explore the board starting from each cell. It checks if the current character (**board[i][j]**) is in the Trie (**p.next[c – ‘a’]**). If not, or if the cell has been visited (**‘#’**), it returns.- If a valid word is found (
**p.word != null**), it adds the word to the result list (**res**) and removes the word from the Trie to avoid duplicates (**p.word = null**). - It marks the current board cell as visited (
**board[i][j] = ‘#’**), recursively explores neighboring cells (up, down, left, right), and then restores the original character after exploration.

**findWords Method**:`findWords`

initializes an empty result list (**res**), builds the Trie using**buildTrie**, and then iterates through each cell in the board, calling**dfs**to find words starting from that cell.

#### 2.2 Time Complexity

:**Trie Construction****O(L)**, where L is the total length of all words combined.:**DFS Traversal****O(m * n * 4**, where m is the number of rows, n is the number of columns in the board, and L is the maximum length of words.^{L})

#### 2.3 Space Complexity

**Trie Structure**:**O(26 * L * N)**, where L is the average length of words and N is the number of words. Each TrieNode has 26 children and may store up to L characters.**DFS Stack**:**O(m * n)**for recursion depth.

**3. Word Search II Leetcode Solution JavaScript**

var findWords = function(board, words) { const res = [], trie = {}; for (let word of words) { let curNode = trie; for (let char of word) { curNode[char] = curNode[char] || {}; curNode[char].count = curNode[char].count + 1 || 1; curNode = curNode[char]; }; curNode.end = word; } for (let row = 0; row < board.length; row++) { for (let col = 0; col < board[row].length; col++) { if (trie[board[row][col]]) traverse(row, col); } } return res; function traverse(row, col, node = trie) { if (!board[row][col]) return; const char = board[row][col], curNode = node[char]; if (!curNode) return; if (curNode.end) { res.push(curNode.end); let toDelete = trie; for (let char of curNode.end) { toDelete[char].count--; if (!toDelete[char].count) { delete(toDelete[char]); break; } toDelete = toDelete[char]; } curNode.end = null; } board[row][col] = 0; (col - 1 >= 0) && traverse(row, col - 1, curNode); (col + 1 < board[row].length) && traverse(row, col + 1, curNode); (row - 1 >= 0) && traverse(row - 1, col, curNode); (row + 1 < board.length) && traverse(row + 1, col, curNode); board[row][col] = char; } };

#### 3.1 Explanation

**Trie Construction**:- The function begins by initializing an empty result array
**res**and an empty Trie**trie**. - It iterates through each word in the
**words**array and constructs the Trie using nested objects (**trie**).

- The function begins by initializing an empty result array
**DFS Traversal (traverse Function)**:- It then iterates through each cell of the
**board**and calls a recursive DFS function**traverse**to search for words starting from each cell. **traverse**checks if the current character on the board exists in the Trie (**node[char]**). If not, it returns.- If a valid word (
**curNode.end**) is found, it adds it to the**res**array and removes it from the Trie to avoid duplicates. - It marks the current board cell as visited (
**board[row][col] = 0**), recursively explores neighboring cells (left, right, up, down), and then restores the original character after exploration.

- It then iterates through each cell of the
**Edge Cases**:- It handles cases where the cell is out of bounds (
**!board[row][col]**) and ensures efficient exploration by marking visited cells (**board[row][col] = 0**).

- It handles cases where the cell is out of bounds (

#### 3.2 Time Complexity

**Trie Construction**:**O(L)**, where L is the total length of all words combined.**DFS Traversal**:**O(m * n * 4**, where m is the number of rows, n is the number of columns in the board, and L is the maximum length of words.^{L})

#### 3.3 Space Complexity

**Trie Structure**:**O(26 * L * N)**, where L is the average length of words and N is the number of words. Each Trie node potentially stores up to 26 children.**DFS Stack**:**O(m * n)**, for recursion depth.

**4. Word Search II Leetcode Solution Python**

class Solution(object): def findWords(self, board, words): m, n = len(board), len(board[0]) dic = defaultdict(set) for i in range(m): for j in range(n): dic[board[i][j]].add((i, j)) results = deque() word, lngth, word_isReversed = '', 0, False def dfs(cord, indx): if indx == lngth: if word_isReversed: results.append(word[::-1]) else: results.append(word) return True ch = word[indx] i, j = cord for cand in [(i - 1, j), (i, j - 1), (i, j + 1), (i + 1, j)]: if cand in dic[ch]: dic[ch].remove(cand) flag = dfs(cand, indx + 1) dic[ch].add(cand) if flag: return True return False ref = set() for i in range(m): for j in range(n - 1): ref.add(board[i][j] + board[i][j + 1]) for j in range(n): for i in range(m - 1): ref.add(board[i][j] + board[i + 1][j]) def check(word): for i in range(len(word) - 1): if word[i] + word[i + 1] not in ref: if word[i + 1] + word[i] not in ref: return False return True for w in words: if check(w): if w[:4] == w[0]*4 or len(dic[w[-1]]) < len(dic[w[0]]): word = w[::-1] word_isReversed = True else: word = w if word_isReversed: word_isReversed = False lngth = len(word) for cord in list(dic[word[0]]): dic[word[0]].remove(cord) flag = dfs(cord, 1) dic[word[0]].add(cord) if flag: break return results

#### 4.1 Explanation

**Initialization**:**m, n**represent the dimensions of the board (**m**rows and**n**columns).**dic**is a**defaultdict**of sets where each character on the board maps to a set of coordinates**(i, j)**where it appears.

**DFS Function (**dfs**)**:- Recursively searches for a word starting from a given position (
**cord**) and index (**indx**) in the word. - Checks neighboring cells (up, down, left, right) to find the next character of the word.
- Uses backtracking (
**dic[ch].remove(cand)**and**dic[ch].add(cand)**) to mark positions as visited and restore them after exploration.

- Recursively searches for a word starting from a given position (
**Validation (check Function)**:- Ensures that adjacent characters in the word exist as adjacent characters on the board (
**ref**set).

- Ensures that adjacent characters in the word exist as adjacent characters on the board (
**Main Logic**:- Iterates through each word in
**words**and checks if it can potentially exist on the board (**check**function). - Determines the direction (normal or reversed) based on conditions (
**w[:4] == w[0]*4**or length of occurrences in**di**`c`

). - Initiates DFS from each valid starting position of the word.

- Iterates through each word in
**Output**:- Appends found words to
**results**using a deque for efficient appending and popping.

- Appends found words to

#### 4.2 Time Complexity

**Trie Construction**:**O(m * n)**, where m is the number of rows and n is the number of columns in the board.**DFS Traversal**:**O(4**, where L is the length of the longest word. In the worst case, each cell might explore four directions.^{L})

#### 4.3 Space Complexity

:**Trie Structure****O(m * n)**for storing board positions in`dic`

and`ref`

.**DFS Stack**:**O(L)**for recursion depth, where L is the length of the longest word.