#include <stdlib.h>
typedef struct Node {
struct Node *children[26];
char *word; // non-NULL means a word ends here
} Node;
static void insert(Node *root, char *word) {
Node *cur = root;
for (char *p = word; *p; p++) {
int i = *p - 'a';
if (!cur->children[i])
cur->children[i] = calloc(1, sizeof(Node));
cur = cur->children[i];
}
cur->word = word;
}
static void destroy(Node *n) {
if (!n)
return;
for (int i = 0; i < 26; i++)
destroy(n->children[i]);
free(n);
}
static void dfs(char **board, int rows, int cols, Node *node, int r, int c,
char **res, int *resSize) {
static const int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
char ch = board[r][c];
Node *next = node->children[ch - 'a'];
if (!next)
return;
if (next->word) {
res[(*resSize)++] = next->word;
next->word = NULL; // avoid duplicates
}
board[r][c] = '#'; // mark visited
for (int d = 0; d < 4; d++) {
int nr = r + dirs[d][0], nc = c + dirs[d][1];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols)
continue;
if (board[nr][nc] == '#')
continue;
dfs(board, rows, cols, next, nr, nc, res, resSize);
}
board[r][c] = ch; // unmark
}
char **findWords(char **board, int boardSize, int *boardColSize, char **words,
int wordsSize, int *returnSize) {
Node *root = calloc(1, sizeof(Node));
for (int i = 0; i < wordsSize; i++)
insert(root, words[i]);
char **res = malloc(wordsSize * sizeof(char *));
*returnSize = 0;
for (int r = 0; r < boardSize; r++)
for (int c = 0; c < boardColSize[0]; c++)
dfs(board, boardSize, boardColSize[0], root, r, c, res, returnSize);
destroy(root);
return res;
}
#include <string>
#include <vector>
using namespace std;
class Solution {
struct Node {
Node *children[26] = {};
string word; // non-empty means a word ends here
};
void insert(Node *root, const string &word) {
Node *cur = root;
for (char ch : word) {
int i = ch - 'a';
if (!cur->children[i])
cur->children[i] = new Node();
cur = cur->children[i];
}
cur->word = word;
}
void dfs(vector<vector<char>> &board, Node *node, int r, int c,
vector<string> &res) {
static constexpr int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
char ch = board[r][c];
Node *next = node->children[ch - 'a'];
if (!next)
return;
if (!next->word.empty()) {
res.push_back(next->word);
next->word.clear(); // avoid duplicates
}
board[r][c] = '#'; // mark visited
int rows = board.size(), cols = board[0].size();
for (auto &d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols)
continue;
if (board[nr][nc] == '#')
continue;
dfs(board, next, nr, nc, res);
}
board[r][c] = ch; // unmark
}
public:
vector<string> findWords(vector<vector<char>> &board, vector<string> &words) {
Node *root = new Node();
for (const string &w : words)
insert(root, w);
vector<string> res;
for (int r = 0; r < (int)board.size(); r++)
for (int c = 0; c < (int)board[0].size(); c++)
dfs(board, root, r, c, res);
return res;
}
};
package tries
type node struct {
children [26]*node
word string // non-empty means a word ends here
}
func (root *node) insert(word string) {
cur := root
for _, ch := range word {
i := ch - 'a'
if cur.children[i] == nil {
cur.children[i] = &node{}
}
cur = cur.children[i]
}
cur.word = word
}
var dirs = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
func dfs(board [][]byte, n *node, r, c int, res *[]string) {
ch := board[r][c]
next := n.children[ch-'a']
if next == nil {
return
}
if next.word != "" {
*res = append(*res, next.word)
next.word = "" // avoid duplicates
}
board[r][c] = '#' // mark visited
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr < 0 || nr >= len(board) || nc < 0 || nc >= len(board[0]) {
continue
}
if board[nr][nc] == '#' {
continue
}
dfs(board, next, nr, nc, res)
}
board[r][c] = ch // unmark
}
func findWords(board [][]byte, words []string) []string {
root := &node{}
for _, w := range words {
root.insert(w)
}
res := []string{}
for r := range board {
for c := range board[0] {
dfs(board, root, r, c, &res)
}
}
return res
}
import java.util.ArrayList;
import java.util.List;
class Solution {
private static class Node {
Node[] children = new Node[26];
String word; // non-null means a word ends here
}
private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private void insert(Node root, String word) {
Node cur = root;
for (char ch : word.toCharArray()) {
int i = ch - 'a';
if (cur.children[i] == null)
cur.children[i] = new Node();
cur = cur.children[i];
}
cur.word = word;
}
private void dfs(char[][] board, Node node, int r, int c, List<String> res) {
char ch = board[r][c];
Node next = node.children[ch - 'a'];
if (next == null)
return;
if (next.word != null) {
res.add(next.word);
next.word = null; // avoid duplicates
}
board[r][c] = '#'; // mark visited
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length)
continue;
if (board[nr][nc] == '#')
continue;
dfs(board, next, nr, nc, res);
}
board[r][c] = ch; // unmark
}
public List<String> findWords(char[][] board, String[] words) {
Node root = new Node();
for (String w : words)
insert(root, w);
List<String> res = new ArrayList<>();
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++)
dfs(board, root, r, c, res);
return res;
}
}
class Node {
constructor() {
this.children = new Map();
this.word = null; // non-null means a word ends here
}
}
const DIRS = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1],
];
function insert(root, word) {
let cur = root;
for (const ch of word) {
if (!cur.children.has(ch)) cur.children.set(ch, new Node());
cur = cur.children.get(ch);
}
cur.word = word;
}
function dfs(board, node, r, c, res) {
const ch = board[r][c];
const next = node.children.get(ch);
if (!next) return;
if (next.word !== null) {
res.push(next.word);
next.word = null; // avoid duplicates
}
board[r][c] = "#"; // mark visited
for (const [dr, dc] of DIRS) {
const nr = r + dr,
nc = c + dc;
if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length)
continue;
if (board[nr][nc] === "#") continue;
dfs(board, next, nr, nc, res);
}
board[r][c] = ch; // unmark
}
/**
* @param {character[][]} board
* @param {string[]} words
* @return {string[]}
*/
var findWords = function (board, words) {
const root = new Node();
for (const w of words) insert(root, w);
const res = [];
for (let r = 0; r < board.length; r++)
for (let c = 0; c < board[0].length; c++) dfs(board, root, r, c, res);
return res;
};
from typing import List, Optional
class Node:
def __init__(self):
self.children: dict[str, "Node"] = {}
self.word: Optional[str] = None # set means a word ends here
DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = Node()
for w in words:
cur = root
for ch in w:
cur = cur.children.setdefault(ch, Node())
cur.word = w
rows, cols = len(board), len(board[0])
res = []
def dfs(node: Node, r: int, c: int) -> None:
ch = board[r][c]
nxt = node.children.get(ch)
if not nxt:
return
if nxt.word:
res.append(nxt.word)
nxt.word = None # avoid duplicates
board[r][c] = "#" # mark visited
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
dfs(nxt, nr, nc)
board[r][c] = ch # unmark
for r in range(rows):
for c in range(cols):
dfs(root, r, c)
return res
#[derive(Default)]
struct Node {
children: [Option<Box<Node>>; 26],
word: Option<String>, // Some means a word ends here
}
const DIRS: [(isize, isize); 4] = [(1, 0), (-1, 0), (0, 1), (0, -1)];
impl Solution {
pub fn find_words(mut board: Vec<Vec<char>>, words: Vec<String>) -> Vec<String> {
let mut root = Node::default();
for w in words {
let mut cur = &mut root;
for b in w.bytes() {
cur = cur.children[(b - b'a') as usize].get_or_insert_with(Default::default);
}
cur.word = Some(w);
}
let mut res = Vec::new();
for r in 0..board.len() {
for c in 0..board[0].len() {
Self::dfs(&mut board, &mut root, r, c, &mut res);
}
}
res
}
fn dfs(board: &mut Vec<Vec<char>>, node: &mut Node, r: usize, c: usize, res: &mut Vec<String>) {
let ch = board[r][c];
if ch == '#' {
return;
}
let Some(next) = node.children[(ch as u8 - b'a') as usize].as_deref_mut() else {
return;
};
if let Some(w) = next.word.take() {
res.push(w); // take() avoids duplicates
}
board[r][c] = '#'; // mark visited
for (dr, dc) in DIRS {
let (Some(nr), Some(nc)) = (r.checked_add_signed(dr), c.checked_add_signed(dc)) else {
continue;
};
if nr < board.len() && nc < board[0].len() {
Self::dfs(board, next, nr, nc, res);
}
}
board[r][c] = ch; // unmark
}
}