Published on

# Word Boggle

Authors

## Problem

Similar with word search problem but the goals is find all words in the board and return with sorted words.

`_5board = [_5 ['R', 'L', 'D'],_5 ['U', 'O', 'E'],_5 ['C', 'S', 'O']_5]`

and `words = ["CODE", "SOLO", "RULES", "COOL"]`, the output should be `solution(board, words) = ["CODE", "RULES"]`.

## Backtracking without trie

`_45import "sort"_45func solution(board [][]string, words []string) []string {_45 result := []string{}_45 for _, word := range words {_45 if canBoggle(board, word, [][2]int{}) {_45 result = append(result, word)_45 }_45 }_45 sort.Strings(result)_45 return result_45}_45_45func canBoggle(board [][]string, word string, used [][2]int) bool {_45 if len(word) == 0 {_45 return true_45 }_45 for i := 0; i < len(board); i++ {_45 for j := 0; j < len(board[0]); j++ {_45 if !isUsed(used, i, j) && board[i][j] == string(word[0]) {_45 if len(used) == 0 || (abs(used[len(used)-1][0]-i) <= 1 && abs(used[len(used)-1][1]-j) <= 1) {_45 if canBoggle(board, word[1:], append(used, [2]int{i, j})) {_45 return true_45 }_45 }_45 }_45 }_45 }_45 return false_45}_45_45func abs(n int) int {_45 if n < 0 {_45 return -n_45 }_45 return n_45}_45_45func isUsed(used [][2]int, i int, j int) bool {_45 for _, coordinate := range used {_45 if coordinate[0] == i && coordinate[1] == j {_45 return true_45 }_45 }_45 return false_45}`

## Backtracking with trie

`_66import "sort"_66type Trie struct {_66 children map[byte]*Trie_66 word string_66}_66_66func (t *Trie) Insert(word string) {_66 node := t_66 for i := range word {_66 ch := word[i]_66 if node.children[ch] == nil {_66 node.children[ch] = &Trie{children: map[byte]*Trie{}}_66 }_66 node = node.children[ch]_66 }_66 node.word = word_66}_66_66var dirs = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, 1}, {-1,-1},{1,-1}}_66_66func solution(board [][]string, words []string) (ans []string) {_66 ans=[]string{}_66 t := &Trie{children: map[byte]*Trie{}}_66 for _, word := range words {_66 t.Insert(word)_66 }_66_66 m, n := len(board), len(board[0])_66_66 var dfs func(node *Trie, x, y int)_66 dfs = func(node *Trie, x, y int) {_66 ch := board[x][y]_66 nxt := node.children[ch[0]]_66 if nxt == nil {_66 return_66 }_66_66 if nxt.word != "" {_66 ans = append(ans, nxt.word)_66 nxt.word = ""_66 }_66_66 if len(nxt.children) > 0 {_66 board[x][y] = "#"_66 for _, d := range dirs {_66 nx, ny := x+d.x, y+d.y_66 if 0 <= nx && nx < m && 0 <= ny && ny < n && board[nx][ny] != "#" {_66 dfs(nxt, nx, ny)_66 }_66 }_66 board[x][y] = ch_66 }_66 _66 if len(nxt.children) == 0 {_66 delete(node.children, ch[0])_66 }_66 }_66 for i, row := range board {_66 for j := range row {_66 dfs(t, i, j)_66 }_66 }_66 sort.Strings(ans)_66_66 return_66}`