Word Search II LeetCode Solution

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

Word Search II LeetCode Solution

Word Search II LeetCode Solution

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.

Word Search II leetcode search1
fig-1
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"]
Word Search II leetcode search2
fig-2
Example 2: (fig-2)
Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

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; } };
Code language: C++ (cpp)

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; } }
Code language: Java (java)

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; } };
Code language: JavaScript (javascript)

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
Code language: Python (python)