Tries for Searching Many Words
Editorial
Every word is its own search
Word Search asks whether one word lies on a board of letters, along a path of side-by-side cells that uses no cell twice. Word Search II hands you a list of words and asks which of them are on the board. The first solution almost everyone writes runs the one-word search once per word. Here it is against one search that carries a trie of all the words, on a 32 × 32 board and some thousands of words, the same in every language:
import time
x = 11 # the same board and words in every language
def next_number():
global x
x = x * 48271 % 2147483647
return x
def letter():
return "abcdefgh"[next_number() % 8]
N = 32
board = [[letter() for _ in range(N)] for _ in range(N)]
words = list(dict.fromkeys("".join(letter() for _ in range(4 + next_number() % 5)) for _ in range(5000)))
print(len(words), "words on a", N, "x", N, "board")
steps_one = 0
def search_one(r, c, word, k): # Word Search: does word[k:] lie on a path from (r, c)?
global steps_one
if r < 0 or c < 0 or r >= N or c >= N or board[r][c] != word[k]:
return False
steps_one += 1
if k == len(word) - 1:
return True
board[r][c] = "#" # used by this path
found = (search_one(r + 1, c, word, k + 1) or search_one(r - 1, c, word, k + 1)
or search_one(r, c + 1, word, k + 1) or search_one(r, c - 1, word, k + 1))
board[r][c] = word[k]
return found
def on_board(word):
for r in range(N):
for c in range(N):
if search_one(r, c, word, 0):
return True
return False
start = time.perf_counter()
found_one = [w for w in words if on_board(w)] # one search per word
one_ms = round((time.perf_counter() - start) * 1000)
class Node:
def __init__(self):
self.children = [None] * 26
self.word = None # the word that ends here, until it's found
steps_trie = 0
found_trie = []
def walk(r, c, node): # one search for every word: carry the trie node along
global steps_trie
if r < 0 or c < 0 or r >= N or c >= N or board[r][c] == "#":
return
here = board[r][c]
child = node.children[ord(here) - ord("a")]
if child is None: # no word goes on with this letter: turn back
return
steps_trie += 1
if child.word is not None:
found_trie.append(child.word)
child.word = None # found once is enough
board[r][c] = "#"
walk(r + 1, c, child)
walk(r - 1, c, child)
walk(r, c + 1, child)
walk(r, c - 1, child)
board[r][c] = here
start = time.perf_counter()
root = Node()
for w in words:
node = root
for ch in w:
i = ord(ch) - ord("a")
if node.children[i] is None:
node.children[i] = Node()
node = node.children[i]
node.word = w
for r in range(N):
for c in range(N):
walk(r, c, root)
trie_ms = round((time.perf_counter() - start) * 1000)
same = "true" if sorted(found_one) == sorted(found_trie) else "false"
print(f"found: {len(found_one)} one word at a time, {len(found_trie)} with the trie, the same words: {same}")
print(f"cells stepped on: {steps_one} one word at a time, {steps_trie} with the trie")
print(f"time: {one_ms} ms one word at a time, {trie_ms} ms with the trie")
# 4891 words on a 32 x 32 board
# found: 2454 one word at a time, 2454 with the trie, the same words: true
# cells stepped on: 718589 one word at a time, 55040 with the trie
# time: 932 ms one word at a time, 75 ms with the trieimport java.util.*;
public class Main {
static long x = 11; // the same board and words in every language
static final int N = 32;
static final char[][] board = new char[N][N];
static long stepsOne = 0, stepsTrie = 0;
static final List<String> foundTrie = new ArrayList<>();
static int nextNumber() {
x = x * 48271 % 2147483647;
return (int) x;
}
static char letter() {
return "abcdefgh".charAt(nextNumber() % 8);
}
static boolean searchOne(int r, int c, String word, int k) { // Word Search: does word[k..] lie on a path from (r, c)?
if (r < 0 || c < 0 || r >= N || c >= N || board[r][c] != word.charAt(k)) return false;
stepsOne++;
if (k == word.length() - 1) return true;
board[r][c] = '#'; // used by this path
boolean found = searchOne(r + 1, c, word, k + 1) || searchOne(r - 1, c, word, k + 1)
|| searchOne(r, c + 1, word, k + 1) || searchOne(r, c - 1, word, k + 1);
board[r][c] = word.charAt(k);
return found;
}
static boolean onBoard(String word) {
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
if (searchOne(r, c, word, 0)) return true;
return false;
}
static class Node {
final Node[] children = new Node[26];
String word; // the word that ends here, until it's found
}
static void walk(int r, int c, Node node) { // one search for every word: carry the trie node along
if (r < 0 || c < 0 || r >= N || c >= N || board[r][c] == '#') return;
char here = board[r][c];
Node child = node.children[here - 'a'];
if (child == null) return; // no word goes on with this letter: turn back
stepsTrie++;
if (child.word != null) {
foundTrie.add(child.word);
child.word = null; // found once is enough
}
board[r][c] = '#';
walk(r + 1, c, child);
walk(r - 1, c, child);
walk(r, c + 1, child);
walk(r, c - 1, child);
board[r][c] = here;
}
public static void main(String[] args) {
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++) board[r][c] = letter();
LinkedHashSet<String> unique = new LinkedHashSet<>();
for (int k = 0; k < 5000; k++) {
int length = 4 + nextNumber() % 5;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < length; i++) sb.append(letter());
unique.add(sb.toString());
}
List<String> words = new ArrayList<>(unique);
System.out.println(words.size() + " words on a " + N + " x " + N + " board");
long start = System.nanoTime();
List<String> foundOne = new ArrayList<>();
for (String w : words) if (onBoard(w)) foundOne.add(w); // one search per word
long oneMs = (System.nanoTime() - start) / 1000000;
start = System.nanoTime();
Node root = new Node();
for (String w : words) {
Node node = root;
for (char ch : w.toCharArray()) {
if (node.children[ch - 'a'] == null) node.children[ch - 'a'] = new Node();
node = node.children[ch - 'a'];
}
node.word = w;
}
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++) walk(r, c, root);
long trieMs = (System.nanoTime() - start) / 1000000;
List<String> a = new ArrayList<>(foundOne), b = new ArrayList<>(foundTrie);
Collections.sort(a);
Collections.sort(b);
System.out.println("found: " + foundOne.size() + " one word at a time, " + foundTrie.size()
+ " with the trie, the same words: " + a.equals(b));
System.out.println("cells stepped on: " + stepsOne + " one word at a time, " + stepsTrie + " with the trie");
System.out.println("time: " + oneMs + " ms one word at a time, " + trieMs + " ms with the trie");
}
}
// 4891 words on a 32 x 32 board
// found: 2454 one word at a time, 2454 with the trie, the same words: true
// cells stepped on: 718589 one word at a time, 55040 with the trie
// time: 50 ms one word at a time, 16 ms with the trie#include <bits/stdc++.h>
using namespace std;
long long x = 11; // the same board and words in every language
const int N = 32;
vector<string> board(N, string(N, ' '));
long long stepsOne = 0, stepsTrie = 0;
vector<string> foundTrie;
int next_number() {
x = x * 48271 % 2147483647;
return (int) x;
}
char letter() {
return "abcdefgh"[next_number() % 8];
}
bool searchOne(int r, int c, const string& word, size_t k) { // Word Search: does word[k..] lie on a path from (r, c)?
if (r < 0 || c < 0 || r >= N || c >= N || board[r][c] != word[k]) return false;
stepsOne++;
if (k == word.size() - 1) return true;
board[r][c] = '#'; // used by this path
bool found = searchOne(r + 1, c, word, k + 1) || searchOne(r - 1, c, word, k + 1)
|| searchOne(r, c + 1, word, k + 1) || searchOne(r, c - 1, word, k + 1);
board[r][c] = word[k];
return found;
}
bool onBoard(const string& word) {
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
if (searchOne(r, c, word, 0)) return true;
return false;
}
struct Node {
Node* children[26] = {};
string word; // the word that ends here, until it's found
};
void walk(int r, int c, Node* node) { // one search for every word: carry the trie node along
if (r < 0 || c < 0 || r >= N || c >= N || board[r][c] == '#') return;
char here = board[r][c];
Node* child = node->children[here - 'a'];
if (!child) return; // no word goes on with this letter: turn back
stepsTrie++;
if (!child->word.empty()) {
foundTrie.push_back(child->word);
child->word.clear(); // found once is enough
}
board[r][c] = '#';
walk(r + 1, c, child);
walk(r - 1, c, child);
walk(r, c + 1, child);
walk(r, c - 1, child);
board[r][c] = here;
}
int main() {
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++) board[r][c] = letter();
vector<string> words;
unordered_set<string> seen;
for (int k = 0; k < 5000; k++) {
int length = 4 + next_number() % 5;
string w;
for (int i = 0; i < length; i++) w += letter();
if (seen.insert(w).second) words.push_back(w);
}
cout << words.size() << " words on a " << N << " x " << N << " board\n";
auto start = chrono::steady_clock::now();
vector<string> foundOne;
for (const string& w : words) if (onBoard(w)) foundOne.push_back(w); // one search per word
long long oneMs = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
start = chrono::steady_clock::now();
Node* root = new Node();
for (const string& w : words) {
Node* node = root;
for (char ch : w) {
if (!node->children[ch - 'a']) node->children[ch - 'a'] = new Node();
node = node->children[ch - 'a'];
}
node->word = w;
}
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++) walk(r, c, root);
long long trieMs = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
vector<string> a = foundOne, b = foundTrie;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
cout << "found: " << foundOne.size() << " one word at a time, " << foundTrie.size()
<< " with the trie, the same words: " << (a == b ? "true" : "false") << "\n";
cout << "cells stepped on: " << stepsOne << " one word at a time, " << stepsTrie << " with the trie\n";
cout << "time: " << oneMs << " ms one word at a time, " << trieMs << " ms with the trie\n";
}
// 4891 words on a 32 x 32 board
// found: 2454 one word at a time, 2454 with the trie, the same words: true
// cells stepped on: 718589 one word at a time, 55040 with the trie
// time: 38 ms one word at a time, 4 ms with the trielet x = 11; // the same board and words in every language
function nextNumber() {
x = x * 48271 % 2147483647;
return x;
}
function letter() {
return "abcdefgh"[nextNumber() % 8];
}
const N = 32;
const board = [];
for (let r = 0; r < N; r++) {
board.push([]);
for (let c = 0; c < N; c++) board[r].push(letter());
}
const unique = new Set();
for (let k = 0; k < 5000; k++) {
const length = 4 + nextNumber() % 5;
let w = "";
for (let i = 0; i < length; i++) w += letter();
unique.add(w);
}
const words = [...unique];
console.log(`${words.length} words on a ${N} x ${N} board`);
let stepsOne = 0;
function searchOne(r, c, word, k) { // Word Search: does word[k..] lie on a path from (r, c)?
if (r < 0 || c < 0 || r >= N || c >= N || board[r][c] !== word[k]) return false;
stepsOne++;
if (k === word.length - 1) return true;
board[r][c] = "#"; // used by this path
const found = searchOne(r + 1, c, word, k + 1) || searchOne(r - 1, c, word, k + 1)
|| searchOne(r, c + 1, word, k + 1) || searchOne(r, c - 1, word, k + 1);
board[r][c] = word[k];
return found;
}
function onBoard(word) {
for (let r = 0; r < N; r++)
for (let c = 0; c < N; c++)
if (searchOne(r, c, word, 0)) return true;
return false;
}
let start = performance.now();
const foundOne = words.filter(onBoard); // one search per word
const oneMs = Math.round(performance.now() - start);
class Node {
constructor() {
this.children = new Array(26).fill(null);
this.word = null; // the word that ends here, until it's found
}
}
let stepsTrie = 0;
const foundTrie = [];
function walk(r, c, node) { // one search for every word: carry the trie node along
if (r < 0 || c < 0 || r >= N || c >= N || board[r][c] === "#") return;
const here = board[r][c];
const child = node.children[here.charCodeAt(0) - 97];
if (child === null) return; // no word goes on with this letter: turn back
stepsTrie++;
if (child.word !== null) {
foundTrie.push(child.word);
child.word = null; // found once is enough
}
board[r][c] = "#";
walk(r + 1, c, child);
walk(r - 1, c, child);
walk(r, c + 1, child);
walk(r, c - 1, child);
board[r][c] = here;
}
start = performance.now();
const root = new Node();
for (const w of words) {
let node = root;
for (const ch of w) {
const i = ch.charCodeAt(0) - 97;
if (node.children[i] === null) node.children[i] = new Node();
node = node.children[i];
}
node.word = w;
}
for (let r = 0; r < N; r++)
for (let c = 0; c < N; c++) walk(r, c, root);
const trieMs = Math.round(performance.now() - start);
const same = [...foundOne].sort().join(" ") === [...foundTrie].sort().join(" ");
console.log(`found: ${foundOne.length} one word at a time, ${foundTrie.length} with the trie, the same words: ${same}`);
console.log(`cells stepped on: ${stepsOne} one word at a time, ${stepsTrie} with the trie`);
console.log(`time: ${oneMs} ms one word at a time, ${trieMs} ms with the trie`);
// 4891 words on a 32 x 32 board
// found: 2454 one word at a time, 2454 with the trie, the same words: true
// cells stepped on: 718589 one word at a time, 55040 with the trie
// time: 73 ms one word at a time, 26 ms with the trielet x = 11; // the same board and words in every language
function nextNumber(): number {
x = x * 48271 % 2147483647;
return x;
}
function letter(): string {
return "abcdefgh"[nextNumber() % 8];
}
const N = 32;
const board: string[][] = [];
for (let r = 0; r < N; r++) {
board.push([]);
for (let c = 0; c < N; c++) board[r].push(letter());
}
const unique = new Set<string>();
for (let k = 0; k < 5000; k++) {
const length = 4 + nextNumber() % 5;
let w = "";
for (let i = 0; i < length; i++) w += letter();
unique.add(w);
}
const words = [...unique];
console.log(`${words.length} words on a ${N} x ${N} board`);
let stepsOne = 0;
function searchOne(r: number, c: number, word: string, k: number): boolean { // Word Search: does word[k..] lie on a path from (r, c)?
if (r < 0 || c < 0 || r >= N || c >= N || board[r][c] !== word[k]) return false;
stepsOne++;
if (k === word.length - 1) return true;
board[r][c] = "#"; // used by this path
const found = searchOne(r + 1, c, word, k + 1) || searchOne(r - 1, c, word, k + 1)
|| searchOne(r, c + 1, word, k + 1) || searchOne(r, c - 1, word, k + 1);
board[r][c] = word[k];
return found;
}
function onBoard(word: string): boolean {
for (let r = 0; r < N; r++)
for (let c = 0; c < N; c++)
if (searchOne(r, c, word, 0)) return true;
return false;
}
let start = performance.now();
const foundOne = words.filter(onBoard); // one search per word
const oneMs = Math.round(performance.now() - start);
class TrieNode {
children: (TrieNode | null)[] = new Array(26).fill(null);
word: string | null = null; // the word that ends here, until it's found
}
let stepsTrie = 0;
const foundTrie: string[] = [];
function walk(r: number, c: number, node: TrieNode): void { // one search for every word: carry the trie node along
if (r < 0 || c < 0 || r >= N || c >= N || board[r][c] === "#") return;
const here = board[r][c];
const child = node.children[here.charCodeAt(0) - 97];
if (child === null) return; // no word goes on with this letter: turn back
stepsTrie++;
if (child.word !== null) {
foundTrie.push(child.word);
child.word = null; // found once is enough
}
board[r][c] = "#";
walk(r + 1, c, child);
walk(r - 1, c, child);
walk(r, c + 1, child);
walk(r, c - 1, child);
board[r][c] = here;
}
start = performance.now();
const root = new TrieNode();
for (const w of words) {
let node = root;
for (const ch of w) {
const i = ch.charCodeAt(0) - 97;
if (node.children[i] === null) node.children[i] = new TrieNode();
node = node.children[i]!;
}
node.word = w;
}
for (let r = 0; r < N; r++)
for (let c = 0; c < N; c++) walk(r, c, root);
const trieMs = Math.round(performance.now() - start);
const same = [...foundOne].sort().join(" ") === [...foundTrie].sort().join(" ");
console.log(`found: ${foundOne.length} one word at a time, ${foundTrie.length} with the trie, the same words: ${same}`);
console.log(`cells stepped on: ${stepsOne} one word at a time, ${stepsTrie} with the trie`);
console.log(`time: ${oneMs} ms one word at a time, ${trieMs} ms with the trie`);
// 4891 words on a 32 x 32 board
// found: 2454 one word at a time, 2454 with the trie, the same words: true
// cells stepped on: 718589 one word at a time, 55040 with the trie
// time: 72 ms one word at a time, 26 ms with the trieusing System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
class Node {
public readonly Node[] Children = new Node[26];
public string Word; // the word that ends here, until it's found
}
class Program {
static long x = 11; // the same board and words in every language
const int N = 32;
static readonly char[,] board = new char[N, N];
static long stepsOne = 0, stepsTrie = 0;
static readonly List<string> foundTrie = new List<string>();
static int NextNumber() {
x = x * 48271 % 2147483647;
return (int) x;
}
static char Letter() => "abcdefgh"[NextNumber() % 8];
static bool SearchOne(int r, int c, string word, int k) { // Word Search: does word[k..] lie on a path from (r, c)?
if (r < 0 || c < 0 || r >= N || c >= N || board[r, c] != word[k]) return false;
stepsOne++;
if (k == word.Length - 1) return true;
board[r, c] = '#'; // used by this path
bool found = SearchOne(r + 1, c, word, k + 1) || SearchOne(r - 1, c, word, k + 1)
|| SearchOne(r, c + 1, word, k + 1) || SearchOne(r, c - 1, word, k + 1);
board[r, c] = word[k];
return found;
}
static bool OnBoard(string word) {
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
if (SearchOne(r, c, word, 0)) return true;
return false;
}
static void Walk(int r, int c, Node node) { // one search for every word: carry the trie node along
if (r < 0 || c < 0 || r >= N || c >= N || board[r, c] == '#') return;
char here = board[r, c];
Node child = node.Children[here - 'a'];
if (child == null) return; // no word goes on with this letter: turn back
stepsTrie++;
if (child.Word != null) {
foundTrie.Add(child.Word);
child.Word = null; // found once is enough
}
board[r, c] = '#';
Walk(r + 1, c, child);
Walk(r - 1, c, child);
Walk(r, c + 1, child);
Walk(r, c - 1, child);
board[r, c] = here;
}
static void Main() {
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++) board[r, c] = Letter();
var words = new List<string>();
var seen = new HashSet<string>();
for (int k = 0; k < 5000; k++) {
int length = 4 + NextNumber() % 5;
var chars = new char[length];
for (int i = 0; i < length; i++) chars[i] = Letter();
string w = new string(chars);
if (seen.Add(w)) words.Add(w);
}
Console.WriteLine($"{words.Count} words on a {N} x {N} board");
var watch = Stopwatch.StartNew();
var foundOne = words.Where(OnBoard).ToList(); // one search per word
long oneMs = watch.ElapsedMilliseconds;
watch.Restart();
var root = new Node();
foreach (string w in words) {
Node node = root;
foreach (char ch in w) {
if (node.Children[ch - 'a'] == null) node.Children[ch - 'a'] = new Node();
node = node.Children[ch - 'a'];
}
node.Word = w;
}
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++) Walk(r, c, root);
long trieMs = watch.ElapsedMilliseconds;
bool same = foundOne.OrderBy(w => w, StringComparer.Ordinal)
.SequenceEqual(foundTrie.OrderBy(w => w, StringComparer.Ordinal));
Console.WriteLine($"found: {foundOne.Count} one word at a time, {foundTrie.Count} with the trie, the same words: {(same ? "true" : "false")}");
Console.WriteLine($"cells stepped on: {stepsOne} one word at a time, {stepsTrie} with the trie");
Console.WriteLine($"time: {oneMs} ms one word at a time, {trieMs} ms with the trie");
}
}
// 4891 words on a 32 x 32 board
// found: 2454 one word at a time, 2454 with the trie, the same words: true
// cells stepped on: 718589 one word at a time, 55040 with the trie
// time: 43 ms one word at a time, 9 ms with the triepackage main
import (
"fmt"
"sort"
"strings"
"time"
)
var x int64 = 11 // the same board and words in every language
const N = 32
var board [N][N]byte
var stepsOne, stepsTrie int
var foundTrie []string
func nextNumber() int {
x = x * 48271 % 2147483647
return int(x)
}
func letter() byte {
return "abcdefgh"[nextNumber()%8]
}
func searchOne(r, c int, word string, k int) bool { // Word Search: does word[k:] lie on a path from (r, c)?
if r < 0 || c < 0 || r >= N || c >= N || board[r][c] != word[k] {
return false
}
stepsOne++
if k == len(word)-1 {
return true
}
board[r][c] = '#' // used by this path
found := searchOne(r+1, c, word, k+1) || searchOne(r-1, c, word, k+1) ||
searchOne(r, c+1, word, k+1) || searchOne(r, c-1, word, k+1)
board[r][c] = word[k]
return found
}
func onBoard(word string) bool {
for r := 0; r < N; r++ {
for c := 0; c < N; c++ {
if searchOne(r, c, word, 0) {
return true
}
}
}
return false
}
type Node struct {
children [26]*Node
word string // the word that ends here, until it's found
}
func walk(r, c int, node *Node) { // one search for every word: carry the trie node along
if r < 0 || c < 0 || r >= N || c >= N || board[r][c] == '#' {
return
}
here := board[r][c]
child := node.children[here-'a']
if child == nil { // no word goes on with this letter: turn back
return
}
stepsTrie++
if child.word != "" {
foundTrie = append(foundTrie, child.word)
child.word = "" // found once is enough
}
board[r][c] = '#'
walk(r+1, c, child)
walk(r-1, c, child)
walk(r, c+1, child)
walk(r, c-1, child)
board[r][c] = here
}
func main() {
for r := 0; r < N; r++ {
for c := 0; c < N; c++ {
board[r][c] = letter()
}
}
words := []string{}
seen := map[string]bool{}
for k := 0; k < 5000; k++ {
length := 4 + nextNumber()%5
b := make([]byte, length)
for i := range b {
b[i] = letter()
}
if w := string(b); !seen[w] {
seen[w] = true
words = append(words, w)
}
}
fmt.Printf("%d words on a %d x %d board\n", len(words), N, N)
start := time.Now()
foundOne := []string{}
for _, w := range words { // one search per word
if onBoard(w) {
foundOne = append(foundOne, w)
}
}
oneMs := time.Since(start).Milliseconds()
start = time.Now()
root := &Node{}
for _, w := range words {
node := root
for i := 0; i < len(w); i++ {
ch := w[i] - 'a'
if node.children[ch] == nil {
node.children[ch] = &Node{}
}
node = node.children[ch]
}
node.word = w
}
for r := 0; r < N; r++ {
for c := 0; c < N; c++ {
walk(r, c, root)
}
}
trieMs := time.Since(start).Milliseconds()
a := append([]string{}, foundOne...)
b := append([]string{}, foundTrie...)
sort.Strings(a)
sort.Strings(b)
same := strings.Join(a, " ") == strings.Join(b, " ")
fmt.Printf("found: %d one word at a time, %d with the trie, the same words: %t\n", len(foundOne), len(foundTrie), same)
fmt.Printf("cells stepped on: %d one word at a time, %d with the trie\n", stepsOne, stepsTrie)
fmt.Printf("time: %d ms one word at a time, %d ms with the trie\n", oneMs, trieMs)
}
// 4891 words on a 32 x 32 board
// found: 2454 one word at a time, 2454 with the trie, the same words: true
// cells stepped on: 718589 one word at a time, 55040 with the trie
// time: 29 ms one word at a time, 7 ms with the trieBoth found the same 2,454 of the 4,891 words in all seven languages. One search per word stepped on 718,589 cells; the trie's one search stepped on 55,040, 13 times fewer. In time that was 932 ms against 75 ms in Python and 38 ms against 4 ms in C++, and the trie was 3 to 12 times faster across the seven languages, building included.
The searches one at a time repeat each other's work. Words that start alike walk the same cells: every word starting with ab steps onto the same a cells and the same b next to them, once per word. The trie does that walk once, for every word that starts that way.
One walk for every word
Put all the words in one trie. Then search the board once, from every cell, and carry a trie node along with the path:
- Step onto a cell only if the current node has a child for its letter, and move to that child. A path on the board is then always a prefix of some word.
- Turn back the moment the node has no child for the letter: no word has this prefix, so nothing further along can be found.
- A node with a word means the path spells it: report the word and take it off the node, so a second path to the same word doesn't report it again.
- While the walk is on a cell, mark it used (here with a
#), and give it its letter back on the way out, as in any backtracking search.
Here it is on a board of three rows, cats, orea and dent, with ten words:
class Node:
def __init__(self):
self.children = [None] * 26
self.word = None # the word that ends here, until it's found
def find_words(rows, words):
board = [list(row) for row in rows]
root = Node()
for w in words: # one trie of all the words
node = root
for ch in w:
i = ord(ch) - ord("a")
if node.children[i] is None:
node.children[i] = Node()
node = node.children[i]
node.word = w
found = []
def walk(r, c, node):
if r < 0 or c < 0 or r >= len(board) or c >= len(board[0]) or board[r][c] == "#":
return
here = board[r][c]
child = node.children[ord(here) - ord("a")]
if child is None: # no word goes on with this letter: turn back
return
if child.word is not None:
found.append(child.word)
child.word = None # found once is enough
board[r][c] = "#" # used by this path
walk(r + 1, c, child)
walk(r - 1, c, child)
walk(r, c + 1, child)
walk(r, c - 1, child)
board[r][c] = here # give the cell its letter back
for r in range(len(board)):
for c in range(len(board[0])):
walk(r, c, root)
return found
words = ["cat", "cats", "care", "core", "cord", "dent", "tent", "rent", "tea", "seat"]
found = find_words(["cats", "orea", "dent"], words)
print("found, in the order the walk met them:", " ".join(found))
print("not found:", " ".join(w for w in words if w not in found))
# found, in the order the walk met them: core care cat cats tent tea rent dent
# not found: cord seatimport java.util.*;
public class Main {
static class Node {
final Node[] children = new Node[26];
String word; // the word that ends here, until it's found
}
static char[][] board;
static List<String> found;
static void walk(int r, int c, Node node) {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] == '#') return;
char here = board[r][c];
Node child = node.children[here - 'a'];
if (child == null) return; // no word goes on with this letter: turn back
if (child.word != null) {
found.add(child.word);
child.word = null; // found once is enough
}
board[r][c] = '#'; // used by this path
walk(r + 1, c, child);
walk(r - 1, c, child);
walk(r, c + 1, child);
walk(r, c - 1, child);
board[r][c] = here; // give the cell its letter back
}
static List<String> findWords(String[] rows, String[] words) {
board = new char[rows.length][];
for (int r = 0; r < rows.length; r++) board[r] = rows[r].toCharArray();
Node root = new Node();
for (String w : words) { // one trie of all the words
Node node = root;
for (char ch : w.toCharArray()) {
if (node.children[ch - 'a'] == null) node.children[ch - 'a'] = new Node();
node = node.children[ch - 'a'];
}
node.word = w;
}
found = new ArrayList<>();
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++) walk(r, c, root);
return found;
}
public static void main(String[] args) {
String[] words = {"cat", "cats", "care", "core", "cord", "dent", "tent", "rent", "tea", "seat"};
List<String> got = findWords(new String[] {"cats", "orea", "dent"}, words);
System.out.println("found, in the order the walk met them: " + String.join(" ", got));
StringJoiner missing = new StringJoiner(" ");
for (String w : words) if (!got.contains(w)) missing.add(w);
System.out.println("not found: " + missing);
}
}
// found, in the order the walk met them: core care cat cats tent tea rent dent
// not found: cord seat#include <bits/stdc++.h>
using namespace std;
struct Node {
Node* children[26] = {};
string word; // the word that ends here, until it's found
};
vector<string> board;
vector<string> found;
void walk(int r, int c, Node* node) {
if (r < 0 || c < 0 || r >= (int) board.size() || c >= (int) board[0].size() || board[r][c] == '#') return;
char here = board[r][c];
Node* child = node->children[here - 'a'];
if (!child) return; // no word goes on with this letter: turn back
if (!child->word.empty()) {
found.push_back(child->word);
child->word.clear(); // found once is enough
}
board[r][c] = '#'; // used by this path
walk(r + 1, c, child);
walk(r - 1, c, child);
walk(r, c + 1, child);
walk(r, c - 1, child);
board[r][c] = here; // give the cell its letter back
}
vector<string> findWords(const vector<string>& rows, const vector<string>& words) {
board = rows;
Node* root = new Node();
for (const string& w : words) { // one trie of all the words
Node* node = root;
for (char ch : w) {
if (!node->children[ch - 'a']) node->children[ch - 'a'] = new Node();
node = node->children[ch - 'a'];
}
node->word = w;
}
found.clear();
for (int r = 0; r < (int) board.size(); r++)
for (int c = 0; c < (int) board[0].size(); c++) walk(r, c, root);
return found;
}
int main() {
vector<string> words = {"cat", "cats", "care", "core", "cord", "dent", "tent", "rent", "tea", "seat"};
vector<string> got = findWords({"cats", "orea", "dent"}, words);
cout << "found, in the order the walk met them:";
for (const string& w : got) cout << " " << w;
cout << "\nnot found:";
for (const string& w : words)
if (find(got.begin(), got.end(), w) == got.end()) cout << " " << w;
cout << "\n";
}
// found, in the order the walk met them: core care cat cats tent tea rent dent
// not found: cord seatclass Node {
constructor() {
this.children = new Array(26).fill(null);
this.word = null; // the word that ends here, until it's found
}
}
function findWords(rows, words) {
const board = rows.map((row) => [...row]);
const root = new Node();
for (const w of words) { // one trie of all the words
let node = root;
for (const ch of w) {
const i = ch.charCodeAt(0) - 97;
if (node.children[i] === null) node.children[i] = new Node();
node = node.children[i];
}
node.word = w;
}
const found = [];
const walk = (r, c, node) => {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] === "#") return;
const here = board[r][c];
const child = node.children[here.charCodeAt(0) - 97];
if (child === null) return; // no word goes on with this letter: turn back
if (child.word !== null) {
found.push(child.word);
child.word = null; // found once is enough
}
board[r][c] = "#"; // used by this path
walk(r + 1, c, child);
walk(r - 1, c, child);
walk(r, c + 1, child);
walk(r, c - 1, child);
board[r][c] = here; // give the cell its letter back
};
for (let r = 0; r < board.length; r++)
for (let c = 0; c < board[0].length; c++) walk(r, c, root);
return found;
}
const words = ["cat", "cats", "care", "core", "cord", "dent", "tent", "rent", "tea", "seat"];
const found = findWords(["cats", "orea", "dent"], words);
console.log("found, in the order the walk met them:", found.join(" "));
console.log("not found:", words.filter((w) => !found.includes(w)).join(" "));
// found, in the order the walk met them: core care cat cats tent tea rent dent
// not found: cord seatclass TrieNode {
children: (TrieNode | null)[] = new Array(26).fill(null);
word: string | null = null; // the word that ends here, until it's found
}
function findWords(rows: string[], words: string[]): string[] {
const board = rows.map((row) => [...row]);
const root = new TrieNode();
for (const w of words) { // one trie of all the words
let node = root;
for (const ch of w) {
const i = ch.charCodeAt(0) - 97;
if (node.children[i] === null) node.children[i] = new TrieNode();
node = node.children[i]!;
}
node.word = w;
}
const found: string[] = [];
const walk = (r: number, c: number, node: TrieNode): void => {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] === "#") return;
const here = board[r][c];
const child = node.children[here.charCodeAt(0) - 97];
if (child === null) return; // no word goes on with this letter: turn back
if (child.word !== null) {
found.push(child.word);
child.word = null; // found once is enough
}
board[r][c] = "#"; // used by this path
walk(r + 1, c, child);
walk(r - 1, c, child);
walk(r, c + 1, child);
walk(r, c - 1, child);
board[r][c] = here; // give the cell its letter back
};
for (let r = 0; r < board.length; r++)
for (let c = 0; c < board[0].length; c++) walk(r, c, root);
return found;
}
const words = ["cat", "cats", "care", "core", "cord", "dent", "tent", "rent", "tea", "seat"];
const found = findWords(["cats", "orea", "dent"], words);
console.log("found, in the order the walk met them:", found.join(" "));
console.log("not found:", words.filter((w) => !found.includes(w)).join(" "));
// found, in the order the walk met them: core care cat cats tent tea rent dent
// not found: cord seatusing System;
using System.Collections.Generic;
using System.Linq;
class Node {
public readonly Node[] Children = new Node[26];
public string Word; // the word that ends here, until it's found
}
class Program {
static char[][] board;
static List<string> found;
static void Walk(int r, int c, Node node) {
if (r < 0 || c < 0 || r >= board.Length || c >= board[0].Length || board[r][c] == '#') return;
char here = board[r][c];
Node child = node.Children[here - 'a'];
if (child == null) return; // no word goes on with this letter: turn back
if (child.Word != null) {
found.Add(child.Word);
child.Word = null; // found once is enough
}
board[r][c] = '#'; // used by this path
Walk(r + 1, c, child);
Walk(r - 1, c, child);
Walk(r, c + 1, child);
Walk(r, c - 1, child);
board[r][c] = here; // give the cell its letter back
}
static List<string> FindWords(string[] rows, string[] words) {
board = rows.Select(row => row.ToCharArray()).ToArray();
var root = new Node();
foreach (string w in words) { // one trie of all the words
Node node = root;
foreach (char ch in w) {
if (node.Children[ch - 'a'] == null) node.Children[ch - 'a'] = new Node();
node = node.Children[ch - 'a'];
}
node.Word = w;
}
found = new List<string>();
for (int r = 0; r < board.Length; r++)
for (int c = 0; c < board[0].Length; c++) Walk(r, c, root);
return found;
}
static void Main() {
string[] words = {"cat", "cats", "care", "core", "cord", "dent", "tent", "rent", "tea", "seat"};
List<string> got = FindWords(new[] {"cats", "orea", "dent"}, words);
Console.WriteLine("found, in the order the walk met them: " + string.Join(" ", got));
Console.WriteLine("not found: " + string.Join(" ", words.Where(w => !got.Contains(w))));
}
}
// found, in the order the walk met them: core care cat cats tent tea rent dent
// not found: cord seatpackage main
import (
"fmt"
"strings"
)
type Node struct {
children [26]*Node
word string // the word that ends here, until it's found
}
var board [][]byte
var found []string
func walk(r, c int, node *Node) {
if r < 0 || c < 0 || r >= len(board) || c >= len(board[0]) || board[r][c] == '#' {
return
}
here := board[r][c]
child := node.children[here-'a']
if child == nil { // no word goes on with this letter: turn back
return
}
if child.word != "" {
found = append(found, child.word)
child.word = "" // found once is enough
}
board[r][c] = '#' // used by this path
walk(r+1, c, child)
walk(r-1, c, child)
walk(r, c+1, child)
walk(r, c-1, child)
board[r][c] = here // give the cell its letter back
}
func findWords(rows []string, words []string) []string {
board = make([][]byte, len(rows))
for r, row := range rows {
board[r] = []byte(row)
}
root := &Node{}
for _, w := range words { // one trie of all the words
node := root
for i := 0; i < len(w); i++ {
ch := w[i] - 'a'
if node.children[ch] == nil {
node.children[ch] = &Node{}
}
node = node.children[ch]
}
node.word = w
}
found = []string{}
for r := range board {
for c := range board[0] {
walk(r, c, root)
}
}
return found
}
func main() {
words := []string{"cat", "cats", "care", "core", "cord", "dent", "tent", "rent", "tea", "seat"}
got := findWords([]string{"cats", "orea", "dent"}, words)
fmt.Println("found, in the order the walk met them:", strings.Join(got, " "))
missing := []string{}
for _, w := range words {
in := false
for _, g := range got {
if g == w {
in = true
}
}
if !in {
missing = append(missing, w)
}
}
fmt.Println("not found:", strings.Join(missing, " "))
}
// found, in the order the walk met them: core care cat cats tent tea rent dent
// not found: cord seatThe walk met core first: from the c at the top left it went down to o, then r, then the e below it. Then care, cat and cats, still from that first c, then tent, tea, rent and dent from later cells. cord isn't on the board, since the r has no d beside it, and neither is seat: the s's only neighbours are t and a.
Walk the Board. Walk the board yourself with the trie beside it: step from cell to cell, watch the trie node follow, see where the walk has to turn back, and find every word.
Why the walk is short
A walk on the board can branch in up to four directions at the first step and three after that, so the paths of length L from one cell grow like . Searching each of k words on an m × n board can try that many paths per word: O(k · m · n · ) in the worst case.
With the trie, each path on the board is walked once for all the words together: the factor k is gone, O(m · n · ) for the walk, plus the total number of letters in the words to build the trie. And that worst case is rarely reached, because a path survives only while it's a prefix of some word, and most paths stop being one within a few letters: in the 32 × 32 example the trie's walk stepped on 55,040 cells for all 4,891 words.
Found once, then cut out
Clearing a found word's mark stops it being reported twice. But its nodes stay in the trie, and the walk keeps following them, though there's nothing left to find down there. On a board where every path matches, that's every path. The fix is to cut a node out of the trie once it has no word and no children left: on the way back out of a cell, if the child it used is empty, remove it from its parent. Here both are run on a 4 × 4 board of a's with the words a, aa, up to aaaaaaaa:
class Node:
def __init__(self):
self.children = [None] * 26
self.kids = 0 # children that exist
self.word = None
def search(rows, words, cut):
board = [list(row) for row in rows]
root = Node()
for w in words:
node = root
for ch in w:
i = ord(ch) - ord("a")
if node.children[i] is None:
node.children[i] = Node()
node.kids += 1
node = node.children[i]
node.word = w
found, steps = [], 0
def walk(r, c, node):
nonlocal steps
if r < 0 or c < 0 or r >= len(board) or c >= len(board[0]) or board[r][c] == "#":
return
here = board[r][c]
i = ord(here) - ord("a")
child = node.children[i]
if child is None:
return
steps += 1
if child.word is not None:
found.append(child.word)
child.word = None
board[r][c] = "#"
walk(r + 1, c, child)
walk(r - 1, c, child)
walk(r, c + 1, child)
walk(r, c - 1, child)
board[r][c] = here
if cut and child.word is None and child.kids == 0: # nothing left to find below it: cut it out
node.children[i] = None
node.kids -= 1
for r in range(len(board)):
for c in range(len(board[0])):
walk(r, c, root)
return len(found), steps
rows = ["aaaa"] * 4
words = ["a" * k for k in range(1, 9)] # a, aa, ..., aaaaaaaa
kept = search(rows, words, False)
cut = search(rows, words, True)
print(f"found: {kept[0]} with found words kept, {cut[0]} with them cut out")
print(f"cells stepped on: {kept[1]} with found words kept, {cut[1]} with them cut out")
# found: 8 with found words kept, 8 with them cut out
# cells stepped on: 4856 with found words kept, 8 with them cut outpublic class Main {
static class Node {
final Node[] children = new Node[26];
int kids; // children that exist
String word;
}
static char[][] board;
static int found, steps;
static boolean cut;
static void walk(int r, int c, Node node) {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] == '#') return;
char here = board[r][c];
Node child = node.children[here - 'a'];
if (child == null) return;
steps++;
if (child.word != null) {
found++;
child.word = null;
}
board[r][c] = '#';
walk(r + 1, c, child);
walk(r - 1, c, child);
walk(r, c + 1, child);
walk(r, c - 1, child);
board[r][c] = here;
if (cut && child.word == null && child.kids == 0) { // nothing left to find below it: cut it out
node.children[here - 'a'] = null;
node.kids--;
}
}
static int[] search(String[] rows, String[] words, boolean cutOut) {
board = new char[rows.length][];
for (int r = 0; r < rows.length; r++) board[r] = rows[r].toCharArray();
Node root = new Node();
for (String w : words) {
Node node = root;
for (char ch : w.toCharArray()) {
if (node.children[ch - 'a'] == null) {
node.children[ch - 'a'] = new Node();
node.kids++;
}
node = node.children[ch - 'a'];
}
node.word = w;
}
found = 0;
steps = 0;
cut = cutOut;
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++) walk(r, c, root);
return new int[] {found, steps};
}
public static void main(String[] args) {
String[] rows = {"aaaa", "aaaa", "aaaa", "aaaa"};
String[] words = new String[8];
for (int k = 1; k <= 8; k++) words[k - 1] = "a".repeat(k); // a, aa, ..., aaaaaaaa
int[] kept = search(rows, words, false);
int[] cutOut = search(rows, words, true);
System.out.println("found: " + kept[0] + " with found words kept, " + cutOut[0] + " with them cut out");
System.out.println("cells stepped on: " + kept[1] + " with found words kept, " + cutOut[1] + " with them cut out");
}
}
// found: 8 with found words kept, 8 with them cut out
// cells stepped on: 4856 with found words kept, 8 with them cut out#include <bits/stdc++.h>
using namespace std;
struct Node {
Node* children[26] = {};
int kids = 0; // children that exist
string word;
};
vector<string> board;
int found, steps;
bool cut;
void walk(int r, int c, Node* node) {
if (r < 0 || c < 0 || r >= (int) board.size() || c >= (int) board[0].size() || board[r][c] == '#') return;
char here = board[r][c];
Node* child = node->children[here - 'a'];
if (!child) return;
steps++;
if (!child->word.empty()) {
found++;
child->word.clear();
}
board[r][c] = '#';
walk(r + 1, c, child);
walk(r - 1, c, child);
walk(r, c + 1, child);
walk(r, c - 1, child);
board[r][c] = here;
if (cut && child->word.empty() && child->kids == 0) { // nothing left to find below it: cut it out
node->children[here - 'a'] = nullptr;
node->kids--;
}
}
pair<int, int> search(const vector<string>& rows, const vector<string>& words, bool cutOut) {
board = rows;
Node* root = new Node();
for (const string& w : words) {
Node* node = root;
for (char ch : w) {
if (!node->children[ch - 'a']) {
node->children[ch - 'a'] = new Node();
node->kids++;
}
node = node->children[ch - 'a'];
}
node->word = w;
}
found = 0;
steps = 0;
cut = cutOut;
for (int r = 0; r < (int) board.size(); r++)
for (int c = 0; c < (int) board[0].size(); c++) walk(r, c, root);
return {found, steps};
}
int main() {
vector<string> rows(4, "aaaa");
vector<string> words;
for (int k = 1; k <= 8; k++) words.push_back(string(k, 'a')); // a, aa, ..., aaaaaaaa
auto kept = search(rows, words, false);
auto cutOut = search(rows, words, true);
cout << "found: " << kept.first << " with found words kept, " << cutOut.first << " with them cut out\n";
cout << "cells stepped on: " << kept.second << " with found words kept, " << cutOut.second << " with them cut out\n";
}
// found: 8 with found words kept, 8 with them cut out
// cells stepped on: 4856 with found words kept, 8 with them cut outclass Node {
constructor() {
this.children = new Array(26).fill(null);
this.kids = 0; // children that exist
this.word = null;
}
}
function search(rows, words, cut) {
const board = rows.map((row) => [...row]);
const root = new Node();
for (const w of words) {
let node = root;
for (const ch of w) {
const i = ch.charCodeAt(0) - 97;
if (node.children[i] === null) {
node.children[i] = new Node();
node.kids++;
}
node = node.children[i];
}
node.word = w;
}
let found = 0, steps = 0;
const walk = (r, c, node) => {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] === "#") return;
const here = board[r][c];
const i = here.charCodeAt(0) - 97;
const child = node.children[i];
if (child === null) return;
steps++;
if (child.word !== null) {
found++;
child.word = null;
}
board[r][c] = "#";
walk(r + 1, c, child);
walk(r - 1, c, child);
walk(r, c + 1, child);
walk(r, c - 1, child);
board[r][c] = here;
if (cut && child.word === null && child.kids === 0) { // nothing left to find below it: cut it out
node.children[i] = null;
node.kids--;
}
};
for (let r = 0; r < board.length; r++)
for (let c = 0; c < board[0].length; c++) walk(r, c, root);
return [found, steps];
}
const rows = ["aaaa", "aaaa", "aaaa", "aaaa"];
const words = Array.from({ length: 8 }, (_, k) => "a".repeat(k + 1)); // a, aa, ..., aaaaaaaa
const kept = search(rows, words, false);
const cut = search(rows, words, true);
console.log(`found: ${kept[0]} with found words kept, ${cut[0]} with them cut out`);
console.log(`cells stepped on: ${kept[1]} with found words kept, ${cut[1]} with them cut out`);
// found: 8 with found words kept, 8 with them cut out
// cells stepped on: 4856 with found words kept, 8 with them cut outclass TrieNode {
children: (TrieNode | null)[] = new Array(26).fill(null);
kids = 0; // children that exist
word: string | null = null;
}
function search(rows: string[], words: string[], cut: boolean): [number, number] {
const board = rows.map((row) => [...row]);
const root = new TrieNode();
for (const w of words) {
let node = root;
for (const ch of w) {
const i = ch.charCodeAt(0) - 97;
if (node.children[i] === null) {
node.children[i] = new TrieNode();
node.kids++;
}
node = node.children[i]!;
}
node.word = w;
}
let found = 0, steps = 0;
const walk = (r: number, c: number, node: TrieNode): void => {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] === "#") return;
const here = board[r][c];
const i = here.charCodeAt(0) - 97;
const child = node.children[i];
if (child === null) return;
steps++;
if (child.word !== null) {
found++;
child.word = null;
}
board[r][c] = "#";
walk(r + 1, c, child);
walk(r - 1, c, child);
walk(r, c + 1, child);
walk(r, c - 1, child);
board[r][c] = here;
if (cut && child.word === null && child.kids === 0) { // nothing left to find below it: cut it out
node.children[i] = null;
node.kids--;
}
};
for (let r = 0; r < board.length; r++)
for (let c = 0; c < board[0].length; c++) walk(r, c, root);
return [found, steps];
}
const rows = ["aaaa", "aaaa", "aaaa", "aaaa"];
const words = Array.from({ length: 8 }, (_, k) => "a".repeat(k + 1)); // a, aa, ..., aaaaaaaa
const kept = search(rows, words, false);
const cut = search(rows, words, true);
console.log(`found: ${kept[0]} with found words kept, ${cut[0]} with them cut out`);
console.log(`cells stepped on: ${kept[1]} with found words kept, ${cut[1]} with them cut out`);
// found: 8 with found words kept, 8 with them cut out
// cells stepped on: 4856 with found words kept, 8 with them cut outusing System;
using System.Linq;
class Node {
public readonly Node[] Children = new Node[26];
public int Kids; // children that exist
public string Word;
}
class Program {
static char[][] board;
static int found, steps;
static bool cut;
static void Walk(int r, int c, Node node) {
if (r < 0 || c < 0 || r >= board.Length || c >= board[0].Length || board[r][c] == '#') return;
char here = board[r][c];
Node child = node.Children[here - 'a'];
if (child == null) return;
steps++;
if (child.Word != null) {
found++;
child.Word = null;
}
board[r][c] = '#';
Walk(r + 1, c, child);
Walk(r - 1, c, child);
Walk(r, c + 1, child);
Walk(r, c - 1, child);
board[r][c] = here;
if (cut && child.Word == null && child.Kids == 0) { // nothing left to find below it: cut it out
node.Children[here - 'a'] = null;
node.Kids--;
}
}
static (int, int) Search(string[] rows, string[] words, bool cutOut) {
board = rows.Select(row => row.ToCharArray()).ToArray();
var root = new Node();
foreach (string w in words) {
Node node = root;
foreach (char ch in w) {
if (node.Children[ch - 'a'] == null) {
node.Children[ch - 'a'] = new Node();
node.Kids++;
}
node = node.Children[ch - 'a'];
}
node.Word = w;
}
found = 0;
steps = 0;
cut = cutOut;
for (int r = 0; r < board.Length; r++)
for (int c = 0; c < board[0].Length; c++) Walk(r, c, root);
return (found, steps);
}
static void Main() {
string[] rows = {"aaaa", "aaaa", "aaaa", "aaaa"};
string[] words = Enumerable.Range(1, 8).Select(k => new string('a', k)).ToArray(); // a, aa, ..., aaaaaaaa
var kept = Search(rows, words, false);
var cutOut = Search(rows, words, true);
Console.WriteLine($"found: {kept.Item1} with found words kept, {cutOut.Item1} with them cut out");
Console.WriteLine($"cells stepped on: {kept.Item2} with found words kept, {cutOut.Item2} with them cut out");
}
}
// found: 8 with found words kept, 8 with them cut out
// cells stepped on: 4856 with found words kept, 8 with them cut outpackage main
import (
"fmt"
"strings"
)
type Node struct {
children [26]*Node
kids int // children that exist
word string
}
var board [][]byte
var found, steps int
var cut bool
func walk(r, c int, node *Node) {
if r < 0 || c < 0 || r >= len(board) || c >= len(board[0]) || board[r][c] == '#' {
return
}
here := board[r][c]
child := node.children[here-'a']
if child == nil {
return
}
steps++
if child.word != "" {
found++
child.word = ""
}
board[r][c] = '#'
walk(r+1, c, child)
walk(r-1, c, child)
walk(r, c+1, child)
walk(r, c-1, child)
board[r][c] = here
if cut && child.word == "" && child.kids == 0 { // nothing left to find below it: cut it out
node.children[here-'a'] = nil
node.kids--
}
}
func search(rows []string, words []string, cutOut bool) (int, int) {
board = make([][]byte, len(rows))
for r, row := range rows {
board[r] = []byte(row)
}
root := &Node{}
for _, w := range words {
node := root
for i := 0; i < len(w); i++ {
ch := w[i] - 'a'
if node.children[ch] == nil {
node.children[ch] = &Node{}
node.kids++
}
node = node.children[ch]
}
node.word = w
}
found, steps, cut = 0, 0, cutOut
for r := range board {
for c := range board[0] {
walk(r, c, root)
}
}
return found, steps
}
func main() {
rows := []string{"aaaa", "aaaa", "aaaa", "aaaa"}
words := []string{}
for k := 1; k <= 8; k++ {
words = append(words, strings.Repeat("a", k)) // a, aa, ..., aaaaaaaa
}
keptFound, keptSteps := search(rows, words, false)
cutFound, cutSteps := search(rows, words, true)
fmt.Printf("found: %d with found words kept, %d with them cut out\n", keptFound, cutFound)
fmt.Printf("cells stepped on: %d with found words kept, %d with them cut out\n", keptSteps, cutSteps)
}
// found: 8 with found words kept, 8 with them cut out
// cells stepped on: 4856 with found words kept, 8 with them cut outBoth found all 8 words. With the found words kept, the walk stepped on 4,856 cells: every path of up to eight a's from every cell is a prefix of aaaaaaaa, so it never had a reason to stop. With them cut out it stepped on 8: the first path found all eight words on its way down, its nodes were cut on the way back up, and the trie was empty before the second cell. Boards like this are where Word Search II solutions without the cut run out of time.
Words at the end of a stream
Stream of Characters turns the question around. Letters arrive one at a time, and after each one you say whether some word ends at the stream's last letters. A trie of the words as they are would have to start a walk at every earlier letter. A trie of the words reversed needs one walk: "the stream ends with a word" becomes "the reversed stream starts with a reversed word", so read the stream from its newest letter backward down the trie. Stop with true at the first end mark, and with false where a node has no child. Never read further back than the longest word:
class Node:
def __init__(self):
self.children = [None] * 26
self.word = None
class StreamChecker:
def __init__(self, words):
self.root = Node()
self.longest = max(len(w) for w in words)
for w in words:
node = self.root
for ch in reversed(w): # the word backwards: its last letter first
i = ord(ch) - ord("a")
if node.children[i] is None:
node.children[i] = Node()
node = node.children[i]
node.word = w
self.stream = []
self.read = 0 # letters the last query read
self.matched = None # the word it found, if any
def query(self, letter):
self.stream.append(letter)
node, self.read, self.matched = self.root, 0, None
# the newest letter first, and never further back than the longest word
for k in range(len(self.stream) - 1, max(-1, len(self.stream) - 1 - self.longest), -1):
node = node.children[ord(self.stream[k]) - ord("a")]
self.read += 1
if node is None:
return False
if node.word is not None:
self.matched = node.word
return True
return False
checker = StreamChecker(["ode", "dex", "code"])
for letter in "codex":
hit = checker.query(letter)
tail = f" ({checker.matched})" if hit else ""
print(f"{letter}: {'true' if hit else 'false'}, read {checker.read} {'letter' if checker.read == 1 else 'letters'}{tail}")
# c: false, read 1 letter
# o: false, read 1 letter
# d: false, read 1 letter
# e: true, read 3 letters (ode)
# x: true, read 3 letters (dex)import java.util.*;
public class Main {
static class Node {
final Node[] children = new Node[26];
String word;
}
static class StreamChecker {
final Node root = new Node();
final int longest;
final StringBuilder stream = new StringBuilder();
int read; // letters the last query read
String matched; // the word it found, if any
StreamChecker(String[] words) {
int most = 0;
for (String w : words) {
most = Math.max(most, w.length());
Node node = root;
for (int k = w.length() - 1; k >= 0; k--) { // the word backwards: its last letter first
int i = w.charAt(k) - 'a';
if (node.children[i] == null) node.children[i] = new Node();
node = node.children[i];
}
node.word = w;
}
longest = most;
}
boolean query(char letter) {
stream.append(letter);
Node node = root;
read = 0;
matched = null;
// the newest letter first, and never further back than the longest word
for (int k = stream.length() - 1; k >= 0 && k > stream.length() - 1 - longest; k--) {
node = node.children[stream.charAt(k) - 'a'];
read++;
if (node == null) return false;
if (node.word != null) {
matched = node.word;
return true;
}
}
return false;
}
}
public static void main(String[] args) {
StreamChecker checker = new StreamChecker(new String[] {"ode", "dex", "code"});
for (char letter : "codex".toCharArray()) {
boolean hit = checker.query(letter);
System.out.println(letter + ": " + hit + ", read " + checker.read + (checker.read == 1 ? " letter" : " letters")
+ (hit ? " (" + checker.matched + ")" : ""));
}
}
}
// c: false, read 1 letter
// o: false, read 1 letter
// d: false, read 1 letter
// e: true, read 3 letters (ode)
// x: true, read 3 letters (dex)#include <bits/stdc++.h>
using namespace std;
struct Node {
Node* children[26] = {};
string word;
};
struct StreamChecker {
Node* root = new Node();
int longest = 0;
string stream;
int read = 0; // letters the last query read
string matched; // the word it found, if any
StreamChecker(const vector<string>& words) {
for (const string& w : words) {
longest = max(longest, (int) w.size());
Node* node = root;
for (int k = (int) w.size() - 1; k >= 0; k--) { // the word backwards: its last letter first
int i = w[k] - 'a';
if (!node->children[i]) node->children[i] = new Node();
node = node->children[i];
}
node->word = w;
}
}
bool query(char letter) {
stream += letter;
Node* node = root;
read = 0;
matched.clear();
// the newest letter first, and never further back than the longest word
for (int k = (int) stream.size() - 1; k >= 0 && k > (int) stream.size() - 1 - longest; k--) {
node = node->children[stream[k] - 'a'];
read++;
if (!node) return false;
if (!node->word.empty()) {
matched = node->word;
return true;
}
}
return false;
}
};
int main() {
StreamChecker checker({"ode", "dex", "code"});
for (char letter : string("codex")) {
bool hit = checker.query(letter);
cout << letter << ": " << (hit ? "true" : "false") << ", read " << checker.read
<< (checker.read == 1 ? " letter" : " letters") << (hit ? " (" + checker.matched + ")" : "") << "\n";
}
}
// c: false, read 1 letter
// o: false, read 1 letter
// d: false, read 1 letter
// e: true, read 3 letters (ode)
// x: true, read 3 letters (dex)class Node {
constructor() {
this.children = new Array(26).fill(null);
this.word = null;
}
}
class StreamChecker {
constructor(words) {
this.root = new Node();
this.longest = Math.max(...words.map((w) => w.length));
for (const w of words) {
let node = this.root;
for (let k = w.length - 1; k >= 0; k--) { // the word backwards: its last letter first
const i = w.charCodeAt(k) - 97;
if (node.children[i] === null) node.children[i] = new Node();
node = node.children[i];
}
node.word = w;
}
this.stream = [];
this.read = 0; // letters the last query read
this.matched = null; // the word it found, if any
}
query(letter) {
this.stream.push(letter);
let node = this.root;
this.read = 0;
this.matched = null;
// the newest letter first, and never further back than the longest word
for (let k = this.stream.length - 1; k >= 0 && k > this.stream.length - 1 - this.longest; k--) {
node = node.children[this.stream[k].charCodeAt(0) - 97];
this.read++;
if (node === null) return false;
if (node.word !== null) {
this.matched = node.word;
return true;
}
}
return false;
}
}
const checker = new StreamChecker(["ode", "dex", "code"]);
for (const letter of "codex") {
const hit = checker.query(letter);
console.log(`${letter}: ${hit}, read ${checker.read} ${checker.read === 1 ? "letter" : "letters"}${hit ? ` (${checker.matched})` : ""}`);
}
// c: false, read 1 letter
// o: false, read 1 letter
// d: false, read 1 letter
// e: true, read 3 letters (ode)
// x: true, read 3 letters (dex)class TrieNode {
children: (TrieNode | null)[] = new Array(26).fill(null);
word: string | null = null;
}
class StreamChecker {
root = new TrieNode();
longest: number;
stream: string[] = [];
read = 0; // letters the last query read
matched: string | null = null; // the word it found, if any
constructor(words: string[]) {
this.longest = Math.max(...words.map((w) => w.length));
for (const w of words) {
let node = this.root;
for (let k = w.length - 1; k >= 0; k--) { // the word backwards: its last letter first
const i = w.charCodeAt(k) - 97;
if (node.children[i] === null) node.children[i] = new TrieNode();
node = node.children[i]!;
}
node.word = w;
}
}
query(letter: string): boolean {
this.stream.push(letter);
let node: TrieNode | null = this.root;
this.read = 0;
this.matched = null;
// the newest letter first, and never further back than the longest word
for (let k = this.stream.length - 1; k >= 0 && k > this.stream.length - 1 - this.longest; k--) {
node = node.children[this.stream[k].charCodeAt(0) - 97];
this.read++;
if (node === null) return false;
if (node.word !== null) {
this.matched = node.word;
return true;
}
}
return false;
}
}
const checker = new StreamChecker(["ode", "dex", "code"]);
for (const letter of "codex") {
const hit = checker.query(letter);
console.log(`${letter}: ${hit}, read ${checker.read} ${checker.read === 1 ? "letter" : "letters"}${hit ? ` (${checker.matched})` : ""}`);
}
// c: false, read 1 letter
// o: false, read 1 letter
// d: false, read 1 letter
// e: true, read 3 letters (ode)
// x: true, read 3 letters (dex)using System;
using System.Linq;
using System.Text;
class Node {
public readonly Node[] Children = new Node[26];
public string Word;
}
class StreamChecker {
readonly Node root = new Node();
readonly int longest;
readonly StringBuilder stream = new StringBuilder();
public int Read; // letters the last query read
public string Matched; // the word it found, if any
public StreamChecker(string[] words) {
longest = words.Max(w => w.Length);
foreach (string w in words) {
Node node = root;
for (int k = w.Length - 1; k >= 0; k--) { // the word backwards: its last letter first
int i = w[k] - 'a';
if (node.Children[i] == null) node.Children[i] = new Node();
node = node.Children[i];
}
node.Word = w;
}
}
public bool Query(char letter) {
stream.Append(letter);
Node node = root;
Read = 0;
Matched = null;
// the newest letter first, and never further back than the longest word
for (int k = stream.Length - 1; k >= 0 && k > stream.Length - 1 - longest; k--) {
node = node.Children[stream[k] - 'a'];
Read++;
if (node == null) return false;
if (node.Word != null) {
Matched = node.Word;
return true;
}
}
return false;
}
}
class Program {
static void Main() {
var checker = new StreamChecker(new[] {"ode", "dex", "code"});
foreach (char letter in "codex") {
bool hit = checker.Query(letter);
Console.WriteLine($"{letter}: {(hit ? "true" : "false")}, read {checker.Read} {(checker.Read == 1 ? "letter" : "letters")}{(hit ? $" ({checker.Matched})" : "")}");
}
}
}
// c: false, read 1 letter
// o: false, read 1 letter
// d: false, read 1 letter
// e: true, read 3 letters (ode)
// x: true, read 3 letters (dex)package main
import "fmt"
type Node struct {
children [26]*Node
word string
}
type StreamChecker struct {
root *Node
longest int
stream []byte
read int // letters the last query read
matched string // the word it found, if any
}
func NewStreamChecker(words []string) *StreamChecker {
s := &StreamChecker{root: &Node{}}
for _, w := range words {
if len(w) > s.longest {
s.longest = len(w)
}
node := s.root
for k := len(w) - 1; k >= 0; k-- { // the word backwards: its last letter first
i := w[k] - 'a'
if node.children[i] == nil {
node.children[i] = &Node{}
}
node = node.children[i]
}
node.word = w
}
return s
}
func (s *StreamChecker) Query(letter byte) bool {
s.stream = append(s.stream, letter)
node := s.root
s.read, s.matched = 0, ""
// the newest letter first, and never further back than the longest word
for k := len(s.stream) - 1; k >= 0 && k > len(s.stream)-1-s.longest; k-- {
node = node.children[s.stream[k]-'a']
s.read++
if node == nil {
return false
}
if node.word != "" {
s.matched = node.word
return true
}
}
return false
}
func main() {
checker := NewStreamChecker([]string{"ode", "dex", "code"})
stream := "codex"
for i := 0; i < len(stream); i++ {
hit := checker.Query(stream[i])
unit := "letters"
if checker.read == 1 {
unit = "letter"
}
tail := ""
if hit {
tail = " (" + checker.matched + ")"
}
fmt.Printf("%c: %t, read %d %s%s\n", stream[i], hit, checker.read, unit, tail)
}
}
// c: false, read 1 letter
// o: false, read 1 letter
// d: false, read 1 letter
// e: true, read 3 letters (ode)
// x: true, read 3 letters (dex)The words ode, dex and code went in backwards: edo, xed, edoc. After c, o and d, one letter was enough to say no: no word ends in c, o or d. After e the walk read e, d, o and met ode's end mark (code ends there too, one letter further back, but one word is all the answer needs). After x it read x, e, d: dex. Each query reads at most as many letters as the longest word, however many words there are and however long the stream gets.
Spotting the pattern
Clues that one trie of all the words is the tool:
- Many words against one board, grid or text, where checking each word on its own repeats the same walk.
- A backtracking search that should stop early: the trie says at every step whether any word still has this prefix.
- Letters arriving one at a time with a question about the last few: reverse the words.
Near misses:
- One word on the board: that's Word Search, plain backtracking, no trie needed.
- Many words, each looked up whole in a list: a hash set answers each in one lookup.
- One pattern in one long text: string matching (KMP, Z), not a trie.
Mistakes that look right
Two of these are run below in every language. The others are just as common:
- The found word's mark isn't cleared: a word that lies on two paths is reported twice.
- The cell isn't given its letter back on the way out: later paths can't use it, and words through it are missed.
- One search per word, which repeats the shared prefixes' walks for every word, as the first example measured.
- A stream checked with the words as they are, or by testing every word against the stream's end: both cost a walk or a comparison per word for every letter.
class Node:
def __init__(self):
self.children = [None] * 26
self.word = None
def find_words(rows, words, clear, give_back):
board = [list(row) for row in rows]
root = Node()
for w in words:
node = root
for ch in w:
i = ord(ch) - ord("a")
if node.children[i] is None:
node.children[i] = Node()
node = node.children[i]
node.word = w
found = []
def walk(r, c, node):
if r < 0 or c < 0 or r >= len(board) or c >= len(board[0]) or board[r][c] == "#":
return
here = board[r][c]
child = node.children[ord(here) - ord("a")]
if child is None:
return
if child.word is not None:
found.append(child.word)
if clear:
child.word = None
board[r][c] = "#"
walk(r + 1, c, child)
walk(r - 1, c, child)
walk(r, c + 1, child)
walk(r, c - 1, child)
if give_back:
board[r][c] = here
for r in range(len(board)):
for c in range(len(board[0])):
walk(r, c, root)
return sorted(found)
rows = ["cats", "orea", "dent"]
words = ["cat", "cats", "care", "core", "cord", "dent", "tent", "rent", "tea", "seat"]
for name, clear, give_back in (("the mark not cleared", False, True), ("the cell not given back", True, False),
("both right", True, True)):
found = find_words(rows, words, clear, give_back)
print(f"{name}: {len(found)} found: {' '.join(found)}")
# the mark not cleared: 11 found: care care cat cats core core dent rent rent tea tent
# the cell not given back: 3 found: cat cats core
# both right: 8 found: care cat cats core dent rent tea tentimport java.util.*;
public class Main {
static class Node {
final Node[] children = new Node[26];
String word;
}
static char[][] board;
static List<String> found;
static boolean clear, giveBack;
static void walk(int r, int c, Node node) {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] == '#') return;
char here = board[r][c];
Node child = node.children[here - 'a'];
if (child == null) return;
if (child.word != null) {
found.add(child.word);
if (clear) child.word = null;
}
board[r][c] = '#';
walk(r + 1, c, child);
walk(r - 1, c, child);
walk(r, c + 1, child);
walk(r, c - 1, child);
if (giveBack) board[r][c] = here;
}
static List<String> findWords(String[] rows, String[] words, boolean clearMark, boolean giveCellBack) {
board = new char[rows.length][];
for (int r = 0; r < rows.length; r++) board[r] = rows[r].toCharArray();
Node root = new Node();
for (String w : words) {
Node node = root;
for (char ch : w.toCharArray()) {
if (node.children[ch - 'a'] == null) node.children[ch - 'a'] = new Node();
node = node.children[ch - 'a'];
}
node.word = w;
}
found = new ArrayList<>();
clear = clearMark;
giveBack = giveCellBack;
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++) walk(r, c, root);
Collections.sort(found);
return found;
}
public static void main(String[] args) {
String[] rows = {"cats", "orea", "dent"};
String[] words = {"cat", "cats", "care", "core", "cord", "dent", "tent", "rent", "tea", "seat"};
String[] names = {"the mark not cleared", "the cell not given back", "both right"};
boolean[][] ways = {{false, true}, {true, false}, {true, true}};
for (int k = 0; k < 3; k++) {
List<String> got = findWords(rows, words, ways[k][0], ways[k][1]);
System.out.println(names[k] + ": " + got.size() + " found: " + String.join(" ", got));
}
}
}
// the mark not cleared: 11 found: care care cat cats core core dent rent rent tea tent
// the cell not given back: 3 found: cat cats core
// both right: 8 found: care cat cats core dent rent tea tent#include <bits/stdc++.h>
using namespace std;
struct Node {
Node* children[26] = {};
string word;
};
vector<string> board;
vector<string> found;
bool clearMark, giveBack;
void walk(int r, int c, Node* node) {
if (r < 0 || c < 0 || r >= (int) board.size() || c >= (int) board[0].size() || board[r][c] == '#') return;
char here = board[r][c];
Node* child = node->children[here - 'a'];
if (!child) return;
if (!child->word.empty()) {
found.push_back(child->word);
if (clearMark) child->word.clear();
}
board[r][c] = '#';
walk(r + 1, c, child);
walk(r - 1, c, child);
walk(r, c + 1, child);
walk(r, c - 1, child);
if (giveBack) board[r][c] = here;
}
vector<string> findWords(const vector<string>& rows, const vector<string>& words, bool clear, bool back) {
board = rows;
Node* root = new Node();
for (const string& w : words) {
Node* node = root;
for (char ch : w) {
if (!node->children[ch - 'a']) node->children[ch - 'a'] = new Node();
node = node->children[ch - 'a'];
}
node->word = w;
}
found.clear();
clearMark = clear;
giveBack = back;
for (int r = 0; r < (int) board.size(); r++)
for (int c = 0; c < (int) board[0].size(); c++) walk(r, c, root);
sort(found.begin(), found.end());
return found;
}
int main() {
vector<string> rows = {"cats", "orea", "dent"};
vector<string> words = {"cat", "cats", "care", "core", "cord", "dent", "tent", "rent", "tea", "seat"};
vector<tuple<string, bool, bool>> ways = {
{"the mark not cleared", false, true}, {"the cell not given back", true, false}, {"both right", true, true}};
for (auto& [name, clear, back] : ways) {
vector<string> got = findWords(rows, words, clear, back);
cout << name << ": " << got.size() << " found:";
for (const string& w : got) cout << " " << w;
cout << "\n";
}
}
// the mark not cleared: 11 found: care care cat cats core core dent rent rent tea tent
// the cell not given back: 3 found: cat cats core
// both right: 8 found: care cat cats core dent rent tea tentclass Node {
constructor() {
this.children = new Array(26).fill(null);
this.word = null;
}
}
function findWords(rows, words, clear, giveBack) {
const board = rows.map((row) => [...row]);
const root = new Node();
for (const w of words) {
let node = root;
for (const ch of w) {
const i = ch.charCodeAt(0) - 97;
if (node.children[i] === null) node.children[i] = new Node();
node = node.children[i];
}
node.word = w;
}
const found = [];
const walk = (r, c, node) => {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] === "#") return;
const here = board[r][c];
const child = node.children[here.charCodeAt(0) - 97];
if (child === null) return;
if (child.word !== null) {
found.push(child.word);
if (clear) child.word = null;
}
board[r][c] = "#";
walk(r + 1, c, child);
walk(r - 1, c, child);
walk(r, c + 1, child);
walk(r, c - 1, child);
if (giveBack) board[r][c] = here;
};
for (let r = 0; r < board.length; r++)
for (let c = 0; c < board[0].length; c++) walk(r, c, root);
return found.sort();
}
const rows = ["cats", "orea", "dent"];
const words = ["cat", "cats", "care", "core", "cord", "dent", "tent", "rent", "tea", "seat"];
for (const [name, clear, giveBack] of [["the mark not cleared", false, true], ["the cell not given back", true, false],
["both right", true, true]]) {
const found = findWords(rows, words, clear, giveBack);
console.log(`${name}: ${found.length} found: ${found.join(" ")}`);
}
// the mark not cleared: 11 found: care care cat cats core core dent rent rent tea tent
// the cell not given back: 3 found: cat cats core
// both right: 8 found: care cat cats core dent rent tea tentclass TrieNode {
children: (TrieNode | null)[] = new Array(26).fill(null);
word: string | null = null;
}
function findWords(rows: string[], words: string[], clear: boolean, giveBack: boolean): string[] {
const board = rows.map((row) => [...row]);
const root = new TrieNode();
for (const w of words) {
let node = root;
for (const ch of w) {
const i = ch.charCodeAt(0) - 97;
if (node.children[i] === null) node.children[i] = new TrieNode();
node = node.children[i]!;
}
node.word = w;
}
const found: string[] = [];
const walk = (r: number, c: number, node: TrieNode): void => {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length || board[r][c] === "#") return;
const here = board[r][c];
const child = node.children[here.charCodeAt(0) - 97];
if (child === null) return;
if (child.word !== null) {
found.push(child.word);
if (clear) child.word = null;
}
board[r][c] = "#";
walk(r + 1, c, child);
walk(r - 1, c, child);
walk(r, c + 1, child);
walk(r, c - 1, child);
if (giveBack) board[r][c] = here;
};
for (let r = 0; r < board.length; r++)
for (let c = 0; c < board[0].length; c++) walk(r, c, root);
return found.sort();
}
const rows = ["cats", "orea", "dent"];
const words = ["cat", "cats", "care", "core", "cord", "dent", "tent", "rent", "tea", "seat"];
const ways: [string, boolean, boolean][] = [["the mark not cleared", false, true],
["the cell not given back", true, false], ["both right", true, true]];
for (const [name, clear, giveBack] of ways) {
const found = findWords(rows, words, clear, giveBack);
console.log(`${name}: ${found.length} found: ${found.join(" ")}`);
}
// the mark not cleared: 11 found: care care cat cats core core dent rent rent tea tent
// the cell not given back: 3 found: cat cats core
// both right: 8 found: care cat cats core dent rent tea tentusing System;
using System.Collections.Generic;
using System.Linq;
class Node {
public readonly Node[] Children = new Node[26];
public string Word;
}
class Program {
static char[][] board;
static List<string> found;
static bool clear, giveBack;
static void Walk(int r, int c, Node node) {
if (r < 0 || c < 0 || r >= board.Length || c >= board[0].Length || board[r][c] == '#') return;
char here = board[r][c];
Node child = node.Children[here - 'a'];
if (child == null) return;
if (child.Word != null) {
found.Add(child.Word);
if (clear) child.Word = null;
}
board[r][c] = '#';
Walk(r + 1, c, child);
Walk(r - 1, c, child);
Walk(r, c + 1, child);
Walk(r, c - 1, child);
if (giveBack) board[r][c] = here;
}
static List<string> FindWords(string[] rows, string[] words, bool clearMark, bool giveCellBack) {
board = rows.Select(row => row.ToCharArray()).ToArray();
var root = new Node();
foreach (string w in words) {
Node node = root;
foreach (char ch in w) {
if (node.Children[ch - 'a'] == null) node.Children[ch - 'a'] = new Node();
node = node.Children[ch - 'a'];
}
node.Word = w;
}
found = new List<string>();
clear = clearMark;
giveBack = giveCellBack;
for (int r = 0; r < board.Length; r++)
for (int c = 0; c < board[0].Length; c++) Walk(r, c, root);
return found.OrderBy(w => w, StringComparer.Ordinal).ToList();
}
static void Main() {
string[] rows = {"cats", "orea", "dent"};
string[] words = {"cat", "cats", "care", "core", "cord", "dent", "tent", "rent", "tea", "seat"};
var ways = new (string, bool, bool)[] {
("the mark not cleared", false, true), ("the cell not given back", true, false), ("both right", true, true)};
foreach (var (name, clearMark, back) in ways) {
List<string> got = FindWords(rows, words, clearMark, back);
Console.WriteLine($"{name}: {got.Count} found: {string.Join(" ", got)}");
}
}
}
// the mark not cleared: 11 found: care care cat cats core core dent rent rent tea tent
// the cell not given back: 3 found: cat cats core
// both right: 8 found: care cat cats core dent rent tea tentpackage main
import (
"fmt"
"sort"
"strings"
)
type Node struct {
children [26]*Node
word string
}
var board [][]byte
var found []string
var clearMark, giveBack bool
func walk(r, c int, node *Node) {
if r < 0 || c < 0 || r >= len(board) || c >= len(board[0]) || board[r][c] == '#' {
return
}
here := board[r][c]
child := node.children[here-'a']
if child == nil {
return
}
if child.word != "" {
found = append(found, child.word)
if clearMark {
child.word = ""
}
}
board[r][c] = '#'
walk(r+1, c, child)
walk(r-1, c, child)
walk(r, c+1, child)
walk(r, c-1, child)
if giveBack {
board[r][c] = here
}
}
func findWords(rows []string, words []string, clear, back bool) []string {
board = make([][]byte, len(rows))
for r, row := range rows {
board[r] = []byte(row)
}
root := &Node{}
for _, w := range words {
node := root
for i := 0; i < len(w); i++ {
ch := w[i] - 'a'
if node.children[ch] == nil {
node.children[ch] = &Node{}
}
node = node.children[ch]
}
node.word = w
}
found, clearMark, giveBack = []string{}, clear, back
for r := range board {
for c := range board[0] {
walk(r, c, root)
}
}
sort.Strings(found)
return found
}
func main() {
rows := []string{"cats", "orea", "dent"}
words := []string{"cat", "cats", "care", "core", "cord", "dent", "tent", "rent", "tea", "seat"}
ways := []struct {
name string
clear, back bool
}{{"the mark not cleared", false, true}, {"the cell not given back", true, false}, {"both right", true, true}}
for _, way := range ways {
got := findWords(rows, words, way.clear, way.back)
fmt.Printf("%s: %d found: %s\n", way.name, len(got), strings.Join(got, " "))
}
}
// the mark not cleared: 11 found: care care cat cats core core dent rent rent tea tent
// the cell not given back: 3 found: cat cats core
// both right: 8 found: care cat cats core dent rent tea tentWithout clearing the mark, care, core and rent came out twice: each lies on two paths, one through the e in the middle row and one through the e in the bottom row. Without giving the cells back, the walk from the first c left its path covered in #'s, and only cat, cats and core were found. With both right, the eight words come out once each.
Check yourself
Quiz
1 / 6Multiple choice
Word Search II with 500 words on one board, solved with one trie of all of them. How many times does the board search run?
Multiple choice
The walk stands on a cell and its trie node has no child for the next cell's letter. What does it do?
Multiple choice
A word lies on two different paths of the board, and the walk doesn't clear a found word's mark. What does it return?
Multiple choice
A 3 × 3 board of a's and the words a, aa and aaa. Without cutting found words out of the trie, the walk steps on 77 cells. How many with them cut out?
Multiple choice
A trie of the words art and tar reversed (tra, rat) checks the stream s, t, a, r, t. After the last t, what does the query answer?
Multiple choice
A stream checker holds 50,000 words of at most 10 letters. At most how many letters can one query read?
Practice
The section's problem for this lesson:
- Word Search II: one trie of all the words, one walk from every cell, found words taken off their nodes and cut out of the trie.
The walk down a trie with a choice at each step comes back in Bitwise Tries: Maximum XOR, over bits instead of letters.