Course4all
Join us on telegram
Home/dsa/Trie/Boggle Game

Boggle Game

Master this topic with zero to advance depth.

Boggle Game

Find the maximum number of words you can find in a Boggle board such that no two words overlap (i.e., they don't share any cell).

Visual Representation

Board: ["abc", "def", "ghi"] Words: ["abc", "defi", "gh"] Possible Selections: 1. {"abc", "def"} -> 2 words 2. {"abc"} -> 1 word Result: 2
Hard

Examples

Input: board = [["a","b","c"],["d","e","f"],["g","h","i"]], words = ["abc","def","gh"]
Output: 2
Approach 1

Level I: Brute Force DFS

Intuition

For each word in the dictionary, perform a standard DFS on the board to see if it exists. Keep track of used cells and try all combinations of non-overlapping words. Very slow but simple.

⏱ O(W * M * N * 4^L)💾 O(M * N)
java
// Standard DFS per word
Approach 2

Level III: Trie + Backtracking (Max Independent Sets)

Intuition

This is a variant of Word Search II. First, find all occurrences of all dictionary words on the board (Word Search II style). Then, treat this as a problem of finding the maximum number of disjoint sets (words) using backtracking. Each word is a set of cell coordinates.

⏱ O(Exp) due to backtracking for disjoint sets.💾 O(N*L)
java
import java.util.*;
class Solution {
    class Node { Node[] children = new Node[26]; boolean isEnd = false; }
    int maxWords = 0;
    public int maxWords(char[][] board, String[] words) {
        Node root = new Node();
        for (String w : words) {
            Node curr = root;
            for (char c : w.toCharArray()) {
                if (curr.children[c-'a'] == null) curr.children[c-'a'] = new Node();
                curr = curr.children[c-'a'];
            }
            curr.isEnd = true;
        }
        List<List<int[]>> allOccurrences = new ArrayList<>();
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                dfsFindAll(board, r, c, root, new ArrayList<>(), allOccurrences);
            }
        }
        backtrackDisjoint(allOccurrences, 0, new boolean[board.length][board[0].length], 0);
        return maxWords;
    }
    private void dfsFindAll(char[][] b, int r, int c, Node n, List<int[]> path, List<List<int[]>> all) {
        char ch = b[r][c];
        if (ch == '#' || n.children[ch-'a'] == null) return;
        n = n.children[ch-'a'];
        path.add(new int[]{r, c});
        if (n.isEnd) all.add(new ArrayList<>(path));
        b[r][c] = '#';
        int[] dr = {0,0,1,-1}, dc = {1,-1,0,0};
        for (int i=0; i<4; i++) {
            int nr = r+dr[i], nc = c+dc[i];
            if (nr>=0 && nr<b.length && nc>=0 && nc<b[0].length) dfsFindAll(b, nr, nc, n, path, all);
        }
        b[r][c] = ch; path.remove(path.size()-1);
    }
    private void backtrackDisjoint(List<List<int[]>> all, int idx, boolean[][] used, int count) {
        maxWords = Math.max(maxWords, count);
        for (int i = idx; i < all.size(); i++) {
            List<int[]> word = all.get(i);
            if (canTake(word, used)) {
                mark(word, used, true);
                backtrackDisjoint(all, i + 1, used, count + 1);
                mark(word, used, false);
            }
        }
    }
    private boolean canTake(List<int[]> word, boolean[][] used) {
        for (int[] p : word) if (used[p[0]][p[1]]) return false;
        return true;
    }
    private void mark(List<int[]> word, boolean[][] used, boolean val) {
        for (int[] p : word) used[p[0]][p[1]] = val;
    }
}
← Previous QuestionWord Break II
Next Question →Stream of Characters