Description
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.
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: []Solution in Python
Python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
self.word = None # Store the complete word at the end node for easy retrieval
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
node.word = word
class Solution:
def findWords(self, board, words):
# Build the Trie from the list of words
trie = Trie()
for word in words:
trie.insert(word)
# Initialize the result list
result = []
# Define the dimensions of the board
rows = len(board)
cols = len(board[0])
# Define the directions for moving in the grid (up, down, left, right)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# Define the backtracking function
def backtrack(r, c, parent):
letter = board[r][c]
curr_node = parent.children[letter]
# Check if we found a word
if curr_node.is_end_of_word:
result.append(curr_node.word)
curr_node.is_end_of_word = False # To avoid duplicate entries
# Mark the current cell as visited
board[r][c] = '#'
# Explore the neighbors in 4 directions
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] in curr_node.children:
backtrack(nr, nc, curr_node)
# Unmark the current cell (backtrack)
board[r][c] = letter
# Optimization: prune the node if it has no children
if not curr_node.children:
parent.children.pop(letter)
# Start backtracking from each cell
for r in range(rows):
for c in range(cols):
if board[r][c] in trie.root.children:
backtrack(r, c, trie.root)
return resultExplanation:
- Trie Construction:
- We use a Trie (prefix tree) to store the list of words. This allows us to quickly check prefixes while traversing the board.
- Backtracking:
- The backtracking function explores all possible directions (up, down, left, right) from the current cell.
- If a valid word is found, it is added to the result list, and the Trie node is marked to avoid duplicate entries.
- Pruning:
- After backtracking, we prune the Trie by removing nodes that no longer lead to any words. This helps optimize the search.
- Handling Edge Cases:
- The algorithm handles the case where the word list is empty, the board is small, or no valid words can be found.
Solution in Javascript
JavaScript
class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
this.word = null; // Store the complete word at the end node for easy retrieval
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
// Insert a word into the Trie
insert(word) {
let node = this.root;
for (let char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.isEndOfWord = true;
node.word = word;
}
}
/**
* @param {character[][]} board
* @param {string[]} words
* @return {string[]}
*/
var findWords = function(board, words) {
// Initialize the Trie and insert all words
const trie = new Trie();
for (let word of words) {
trie.insert(word);
}
// Result array to store found words
const result = [];
// Get the dimensions of the board
const rows = board.length;
const cols = board[0].length;
// Directions for moving in the grid (up, down, left, right)
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
// Define the backtracking function
function backtrack(r, c, parent) {
let letter = board[r][c];
let currNode = parent.children[letter];
// Check if we found a word
if (currNode.isEndOfWord) {
result.push(currNode.word);
currNode.isEndOfWord = false; // Avoid duplicate entries
}
// Mark the current cell as visited
board[r][c] = '#';
// Explore the neighbors in 4 directions
for (let [dr, dc] of directions) {
let nr = r + dr;
let nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] in currNode.children) {
backtrack(nr, nc, currNode);
}
}
// Unmark the current cell (backtrack)
board[r][c] = letter;
// Optimization: prune the node if it has no children
if (Object.keys(currNode.children).length === 0) {
delete parent.children[letter];
}
}
// Start backtracking from each cell on the board
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (board[r][c] in trie.root.children) {
backtrack(r, c, trie.root);
}
}
}
return result;
};Solution in Java
Java
import java.util.ArrayList;
import java.util.List;
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEndOfWord = false;
String word = null;
}
class Trie {
TrieNode root = new TrieNode();
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEndOfWord = true;
node.word = word;
}
}
class Solution {
private List<String> result = new ArrayList<>();
private int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private int rows;
private int cols;
public List<String> findWords(char[][] board, String[] words) {
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
rows = board.length;
cols = board[0].length;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (trie.root.children[board[r][c] - 'a'] != null) {
backtrack(r, c, trie.root, board);
}
}
}
return result;
}
private void backtrack(int r, int c, TrieNode parent, char[][] board) {
char letter = board[r][c];
TrieNode currNode = parent.children[letter - 'a'];
if (currNode.isEndOfWord) {
result.add(currNode.word);
currNode.isEndOfWord = false;
}
board[r][c] = '#';
for (int[] direction : directions) {
int nr = r + direction[0];
int nc = c + direction[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] != '#' && currNode.children[board[nr][nc] - 'a'] != null) {
backtrack(nr, nc, currNode, board);
}
}
board[r][c] = letter;
if (isLeafNode(currNode)) {
parent.children[letter - 'a'] = null;
}
}
private boolean isLeafNode(TrieNode node) {
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
return false;
}
}
return true;
}
}Solution in C#
C#
using System;
using System.Collections.Generic;
public class TrieNode {
// Map each character to its corresponding TrieNode
public TrieNode[] children = new TrieNode[26];
// Flag to indicate if this node represents the end of a word
public bool isEndOfWord = false;
// Store the complete word at the end node for easy retrieval
public string word = null;
}
public class Trie {
// The root node of the Trie
public TrieNode root = new TrieNode();
// Method to insert a word into the Trie
public void Insert(string word) {
TrieNode node = root;
foreach (char c in word) {
int index = c - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEndOfWord = true;
node.word = word;
}
}
public class Solution {
private IList<string> result = new List<string>();
private int[][] directions = new int[][] {
new int[] {-1, 0}, // up
new int[] {1, 0}, // down
new int[] {0, -1}, // left
new int[] {0, 1} // right
};
private int rows;
private int cols;
public IList<string> FindWords(char[][] board, string[] words) {
// Initialize the Trie and insert all words
Trie trie = new Trie();
foreach (string word in words) {
trie.Insert(word);
}
// Get the dimensions of the board
rows = board.Length;
cols = board[0].Length;
// Start backtracking from each cell on the board
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (trie.root.children[board[r][c] - 'a'] != null) {
Backtrack(r, c, trie.root, board);
}
}
}
return result;
}
private void Backtrack(int r, int c, TrieNode parent, char[][] board) {
char letter = board[r][c];
TrieNode currNode = parent.children[letter - 'a'];
// Check if we have found a word
if (currNode.isEndOfWord) {
result.Add(currNode.word);
currNode.isEndOfWord = false; // Avoid duplicate entries
}
// Mark the current cell as visited by replacing the letter with a special character
board[r][c] = '#';
// Explore the neighbors in 4 directions
foreach (int[] direction in directions) {
int nr = r + direction[0];
int nc = c + direction[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] != '#' && currNode.children[board[nr][nc] - 'a'] != null) {
Backtrack(nr, nc, currNode, board);
}
}
// Unmark the current cell (backtrack)
board[r][c] = letter;
// Optimization: prune the node if it has no children
if (IsLeafNode(currNode)) {
parent.children[letter - 'a'] = null;
}
}
// Helper function to check if a TrieNode is a leaf node (has no children)
private bool IsLeafNode(TrieNode node) {
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
return false;
}
}
return true;
}
}