Word Boggle
February 5, 2023
Problem
Similar with word search (opens in a new tab) problem but the goals is find all words in the board and return with sorted words.
board = [ ['R', 'L', 'D'], ['U', 'O', 'E'], ['C', 'S', 'O']]
and words = ["CODE", "SOLO", "RULES", "COOL"]
, the output should be
solution(board, words) = ["CODE", "RULES"]
.
Backtracking without trie
import "sort"func solution(board [][]string, words []string) []string { result := []string{} for _, word := range words { if canBoggle(board, word, [][2]int{}) { result = append(result, word) } } sort.Strings(result) return result}func canBoggle(board [][]string, word string, used [][2]int) bool { if len(word) == 0 { return true } for i := 0; i < len(board); i++ { for j := 0; j < len(board[0]); j++ { if !isUsed(used, i, j) && board[i][j] == string(word[0]) { if len(used) == 0 || (abs(used[len(used)-1][0]-i) <= 1 && abs(used[len(used)-1][1]-j) <= 1) { if canBoggle(board, word[1:], append(used, [2]int{i, j})) { return true } } } } } return false}func abs(n int) int { if n < 0 { return -n } return n}func isUsed(used [][2]int, i int, j int) bool { for _, coordinate := range used { if coordinate[0] == i && coordinate[1] == j { return true } } return false}
Backtracking with trie
import "sort"type Trie struct { children map[byte]*Trie word string}func (t *Trie) Insert(word string) { node := t for i := range word { ch := word[i] if node.children[ch] == nil { node.children[ch] = &Trie{children: map[byte]*Trie{}} } node = node.children[ch] } node.word = word}var dirs = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, 1}, {-1,-1},{1,-1}}func solution(board [][]string, words []string) (ans []string) { ans=[]string{} t := &Trie{children: map[byte]*Trie{}} for _, word := range words { t.Insert(word) } m, n := len(board), len(board[0]) var dfs func(node *Trie, x, y int) dfs = func(node *Trie, x, y int) { ch := board[x][y] nxt := node.children[ch[0]] if nxt == nil { return } if nxt.word != "" { ans = append(ans, nxt.word) nxt.word = "" } if len(nxt.children) > 0 { board[x][y] = "#" for _, d := range dirs { nx, ny := x+d.x, y+d.y if 0 <= nx && nx < m && 0 <= ny && ny < n && board[nx][ny] != "#" { dfs(nxt, nx, ny) } } board[x][y] = ch } if len(nxt.children) == 0 { delete(node.children, ch[0]) } } for i, row := range board { for j := range row { dfs(t, i, j) } } sort.Strings(ans) return}