Boggle - find words in matrix of letters

Given a collection of words, find which of the words exist in a matrix of letters. You can move downwards, to the left and diagonally.

image


Example:
Given the matrix bellow, find the words “ALL” and “LOL”

A G H N
U L O A
N M L K
L B V M

Approach (Brute Force)

The brute force is to iterate over all possible word combinations, and look up the input worlds in every possible word combination. If you know how to iterate recursively though a grid that’s fairly straight forward, but it’s also inefficient. 
  • Iterate through all the cells
    • For each cell,
      • Call FindWordRecursive, injecting the cell’s row, column and a new empty buffer (StringBuilder)
      • (Base Case) Break if the cell’s row, column outside the matrix
      • FindWordRecursive clones the input buffer and adds the char located at row, column
      • Check if the string composed by the new input buffer appears in the in the given collection of words, if yes, add the word the result
      • (Optimization of stopping point) Can we do another check to stop the recursion early?
      • FindWordRecursive call itself, passing the the row, column position of the cell downward (row +1 , column) and the new buffer
      • FindWordRecursive call itself, passing the the row, column position of the cell to the right (row, column+1) and the new buffer
      • FindWordRecursive call itself, passing the the row, column position of the diagonal cell (row+1, column+1) and the new buffer

    Approach (Brute Force Optimized)

    Instead of iterating though all possible word combinations in the matrix, we can iterate through the words collection, and lookup every word (char after char) in the matrix.

    Approach (Trie)

    A better approach would be to build a trie tree from the matrix, and look up every word in the words collection using the trie.

    Tests

    public class FindWordsTest {
        private static final FinderType FINDER_TYPE = FinderType.Trie;
        @Test
        public void findWordsInMatrix_allWordsExist() throws Exception {
            WordsFinder finder = createWordsFinder(FINDER_TYPE);
    
            char[][] matrix = getMatrix();
    
            final String[] lookupList = {"ALL", "LOL"};
            final List<String> results = finder.findWordsInMatrix(new Matrix(matrix), lookupList);
            assertArrayEquals(lookupList, results.toArray(new String[0]));
        }
    
        @Test
        public void findWordsInMatrix_someWordsExist() throws Exception {
            WordsFinder finder = createWordsFinder(FINDER_TYPE);
    
            char[][] matrix = getMatrix();
    
            final String[] lookupList = {"ALL", "LOL", "LOAN"};
            final List<String> results = finder.findWordsInMatrix(new Matrix(matrix), lookupList);
    
            final String[] expectedList = {"ALL", "LOL"};
            assertArrayEquals(expectedList, results.toArray(new String[0]));
        }
    
        @Test
        public void findWordsInMatrix_noWordExist() throws Exception {
            WordsFinder finder = createWordsFinder(FINDER_TYPE);
            char[][] matrix = getMatrix();
    
            final String[] lookupList = {"MLL", "MOL"};
            final List<String> results = finder.findWordsInMatrix(new Matrix(matrix), lookupList);
    
            final String[] expectedList = {};
            assertArrayEquals(expectedList, results.toArray(new String[0]));
        }
    
        private char[][] getMatrix() {
            char[][] matrix = new char[4][];
            matrix[0] = new char[] {'A', 'G', 'H', 'N'};
            matrix[1] = new char[] { 'U', 'L', 'O', 'A' };
            matrix[2] = new char[] { 'N', 'M', 'L', 'K' };
            matrix[3] = new char[] { 'L', 'B', 'V', 'M' };
            return matrix;
        }
    
        private WordsFinder createWordsFinder(FinderType finderType) {
            if (finderType == FinderType.Brute)
            {
                return new WordsFinderBruteForce();
            }
            return new WordsFinderWithTrie();
        }
    
        enum FinderType{
            Brute,
            Trie
        }
    }

    Solution (Brute force)

    public class WordsFinderBruteForce implements WordsFinder{
        @Override
        public List<String> findWordsInMatrix(Matrix matrix, String[] lookupList){
            final int rows = matrix.rows;
            final int columns = matrix.columns;
    
            if (rows == 0 || columns == 0)
            {
                return new ArrayList<>();
            }
    
            List<String> result = new ArrayList<>();
    
            for (int row = 0; row < rows; row++) {
                for (int column = 0; column < columns; column++) {
                    StringBuilder buffer = new StringBuilder();
                    findWordRecursive(matrix, lookupList, row, column, buffer, result);
                }
            }
    
            return result;
        }
    
        private static void findWordRecursive(
                Matrix matrix,
                String[] lookupList,
                int row,
                int column,
                StringBuilder buffer,
                List<String> result) {
    
            // Base case - check if point is out of range
            Boolean inRange = matrix.isInRange(row, column);
            if (!inRange){
                return;
            }
    
            StringBuilder newBuffer = new StringBuilder();
            newBuffer.append(buffer);
            newBuffer.append(matrix.get(row, column));
    
            // Check if we found the word
            final String newWord = newBuffer.toString();
            Boolean wordFound = checkIfWordInList(newWord, lookupList);
            if (wordFound){
                result.add(newWord);
            }
    
            // Look down
            findWordRecursive(matrix, lookupList, row+1, column, newBuffer, result);
    
            // Look right
            findWordRecursive(matrix, lookupList, row, column+1, newBuffer, result);
    
            // Look diagonal
            findWordRecursive(matrix, lookupList, row+1, column+1, newBuffer, result);
        }
    
        private static Boolean checkIfWordInList(String s, String[] lookupList) {
            for (String lookupItem : lookupList) {
                if (lookupItem.equals(s)) {
                    return true;
                }
            }
            return false;
        }
    }

    Solution (Trie)

    public class WordsFinderWithTrie implements WordsFinder {
        @Override
        public List<String> findWordsInMatrix(Matrix matrix, String[] lookupList) {
            List<String> result = new ArrayList<>();
            if (matrix.rows == 0 || matrix.columns == 0)
            {
                return result;
            }
            TrieNode trie = buildTrie(matrix);
    
            for (String lookupWord : lookupList) {
                Boolean exist = isWordInTrie(lookupWord, trie);
                if (exist) {
                    result.add(lookupWord);
                }
            }
            return result;
        }
    
        private Boolean isWordInTrie(String word, TrieNode trie) {
            TrieNode nextNode = trie;
            for (int i = 0; i < word.length(); i++) {
                Character c = word.charAt(i);
                TrieNode currentNode = nextNode.getNode(c);
                if (currentNode == null)
                {
                    return false;
                }
                nextNode = currentNode;
            }
            return true;
        }
    
        private TrieNode buildTrie(Matrix matrix) {
            TrieNode trie = new TrieNode(null);
            final int rows = matrix.rows;
            final int columns = matrix.columns;
    
            for (int row = 0; row < rows; row++) {
                for (int column = 0; column < columns; column++) {
                    buildTrieRecursive(matrix, trie, row, column);
                }
            }
            return trie;
        }
    
        private void buildTrieRecursive(Matrix matrix, TrieNode trie, int row, int column) {
            // Base case: check if the position in in matrix range
            Boolean inRange = matrix.isInRange(row, column);
            if (!inRange) {
                return;
            }
            final TrieNode child = trie.addChild(matrix.get(row, column));
    
            buildTrieRecursive(matrix, child, row + 1, column);
            buildTrieRecursive(matrix, child, row, column + 1);
            buildTrieRecursive(matrix, child, row + 1, column + 1);
        }
    }

    Data Structures

    public class Matrix {
        private char[][] matrix;
        int rows, columns;
    
        public Matrix(char[][] matrix) {
            this.matrix = matrix;
            rows = matrix.length;
            columns = matrix.length == 0 ? 0 : matrix[0].length;
        }
    
        public Character get(int row, int column) {
            return matrix[row][column];
        }
    
        public Boolean isInRange(int row, int column) {
            return row >= 0 &&
                    column >=0 &&
                    row < rows &&
                    column < columns;
        }
    }
    public class TrieNode {
        Character data;
        private HashMap<Character, TrieNode> nodes = new HashMap<>();
    
        public TrieNode(Character data) {
            this.data = data;
        }
    
        public Character getData() {
            return data;
        }
    
        public TrieNode getNode(Character key) {
            return nodes.get(key);
        }
    
        public TrieNode addChild(Character key) {
            TrieNode node = getNode(key);
            if (node == null)
            {
                node = new TrieNode(key);
                nodes.put(key, node);
            }
            return node;
        }
    }

    Comments