Word Boggle

February 5, 2023

Name: Moch Lutfi
Twitter: @kaptenupi

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
}

N Queens Single linked list trick collection