Why would you use Trie data structure in WordSearch problem given below?

Question

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Word Search Problem

Answer 1

word search 1: search one word in a grid.

word search requires looking up the word, starting from each of the cells.

optimization 1: use backtracking to terminate invalid searches early on and to reuse partial matches in searches.

word search 2: search multiple words in a grid.

for each of the word, apply backtracking.

optimization 2: in one parse of the grid, lookup up all the words at once. at each cell, trie helps figure out if any of the words match.

Answer 2

The reason you might want to use a Trie is that you can use a TRIE to index the entire board (though creating this trie is not trivial) after you created the trie you can find any word in it in O(1) time

board = { T H
          M E}

trieBeforeDict = 
-root-
 |------------------------------\--------------\--\
 T                               H              M   E
 |------                         |                 ..etc..
 |-------\---\                   \--\--\  
 H        M   E                   T  M  E   
 |--\      ..etc..                 ..etc..
 M  E
 |  |
 E  M

traverse with dictionary
* marks isWord attribute

trieAfterDict = 
-root-
 |--\--\
 T  H  M  
 |  |  |
 |  E* E* 
 H  |  
 |  M*
 |  
 E*
 |
 M*

After initialization you can discard the board and dictionary and any future lookups will be very fast and the memory overhead is low.

A reason to want this could be that you want to minimize overhead in a game and have the option of precompiling the 'game' in development, and ship the 'compiled' trie to production

Answer 3

Here is an alternative solution with an enhanced Node structure which makes the code simpler.
I'll leave it up to you to decide which is better for your needs:

import java.util.*;

public class Solution {

    private char[][] board = null;
    private boolean[][] visited = null;
    private final Set<String> result = new HashSet<>();
    int[][]directions = {{0,1},{1,0},{0,-1},{-1,0}};

    public List<String> findWords(char[][] board, String[] words) {

        List<Node> wordsAsNodes = new ArrayList<>();
        for (String word : words) {
            wordsAsNodes.add(new Node(word));
        }

        this.board = board;

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                final int ii=i, jj=j;
                wordsAsNodes.forEach(node->{
                    if(node.c == board[ii][jj]){
                        visited = initializeVisited();
                        dfs(ii, jj, node);
                    }
                });
            }
        }

        return new ArrayList<>(result);
    }

    private boolean[][] initializeVisited() {
        visited = new boolean[board.length][board[0].length];
        for(boolean[] row : visited){
            Arrays.fill(row, false);
        }
        return visited;
    }

    private void dfs(int row, int col, Node node) {

        if (node == null || row < 0 || col < 0 || row >= board.length ||
                            col >= board[0].length || visited[row][col]) return;

        char letter = board[row][col];
        if (node.c != letter) return;
        visited[row][col] = true;

        Node nextNode = node.getNext();
        // check if there is any match
        if (nextNode == null) {
            result.add(node.word);
            return;
        }

        // explore neighbor cells in 4 directions
        for(int[] dir : directions){
            dfs(row + dir[0], col + dir[1], nextNode);
        }
        //if no solution found mark as unvisited for following attempts
        visited[row][col] = false;
    }

    public static void main(String[] args) {

        Solution a = new Solution();
        char[][] board1 ={
                {'o','a','a','n'},
                {'e','t','a','e'},
                {'i','h','k','r'},
                {'i','f','l','v'}
        };

        String [] words1 = {"oath","pea","eat","rain"};

        System.out.println(a.findWords(board1, words1));
    }
}

class Node {

    final String word;
    private final int index;
    private Node parent, next;
    char c;

    public Node(String word) {
        this(word,0);
    }

    private Node(String word, int index) {

        this.word = Objects.requireNonNull(word, "word should not be null");
        this.index = index;
        c = word.charAt(index);
    }

    private Node next() {
        return index +1 < word.length()  ? new Node(word, index+1) : null;
    }

    private Node parent() {
        return index -1 >= 0  ? new Node(word, index-1) : null;
    }

    Node getParent() {
        return parent == null ? parent = parent(): parent;
    }

    Node getNext() {
        return next == null ? next = next(): next;
    }

    @Override
    public String toString() {
        return c +" index "+ index + " in "  + word ;
    }
}

Answer 4

Brute Force Approach : Time Complexity will be O(num. of words * M * 4 * 3^L-1)

1. M = number of cells in the 2D matrix
2. L = length ofmaximum length of words.

    public class WordSearchII {
      int flag = 0;
    
      public List<String> findWords(char[][] b, String[] words) {
        List<String> result = new ArrayList<>();
        for (int k = 0; k < words.length; k++) {
          flag = 0;
          /*
           * Find word's first letter. Then call method to check it's surroundings
           */
          for (int r = 0; r < b.length; r++) {
            for (int c = 0; c < b[0].length; c++) {
              if (b[r][c] == words[k].charAt(0) && dfs(b, words[k], 0, r, c)) {
                if (flag == 1) {
                  result.add(words[k]);
                  break;
                }
              }
            }
            if (flag == 1) {
              break;
            }
          }
        }
        return result;
        // return new ArrayList<>(new HashSet<>(result));
      }
    
      public boolean dfs(char[][] b, String word, int start, int r, int c) {
        /* once we get past word.length, we are done. */
        if (word.length() <= start) {
          flag = 1;
          return true;
        }
        /*
         * if off bounds, letter is seen, letter is unequal to word.charAt(start)
         * return false
         */
        if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] == '0' || b[r][c] != word.charAt(start))
          return false;
    
        /* set this board position to seen. (Because we can use this postion) */
        char tmp = b[r][c];
        b[r][c] = '0';
    
        /* recursion on all 4 sides for next letter, if works: return true */
        if (dfs(b, word, start + 1, r + 1, c) || dfs(b, word, start + 1, r - 1, c) || dfs(b, word, start + 1, r, c + 1)
            || dfs(b, word, start + 1, r, c - 1)) {
          // Set back to unseen
          b[r][c] = tmp;
          return true;
        }
    
        // Set back to unseen
        b[r][c] = tmp;
    
        return false;
      }
    }

Trie-based approach

1. Time Complexity reduces to O(M * 4 * 3^L-1)
2. Introduces need for space O(2N); in case of worst case when Trie would have as many nodes as the letters of all words, where N is the total number of letters. Because we also store strings to be searched N becomes 2N

public class WordSearchIIWithTwist {
  char[][] _board = null;
  ArrayList<String> _result = new ArrayList<String>();
  TrieNode root = new TrieNode();

  public List<String> findWords(char[][] board, String[] words) {

    // Step 1). Construct the Trie
    for (int i = 0; i < words.length; i++) {
      char[] arr = words[i].toCharArray();
      TrieNode current = root;
      for (int j = 0; j < arr.length; j++) {
        if (!current.children.containsKey(arr[j])) {
          current.children.put(arr[j], new TrieNode());
        }
        current = current.children.get(arr[j]);
      }
      current.word = words[i];
    }

    this._board = board;

    // Step 2). Backtracking starting for each cell in the board
    for (int i = 0; i < board.length; i++) {
      for (int j = 0; j < board[0].length; j++) {
        if (root.children.containsKey(board[i][j])) {
          dfs(i, j, root);
        }
      }
    }
    return _result;
  }

  private void dfs(int row, int col, TrieNode parent) {

    if (row < 0 || col < 0 || row >= _board.length || col >= _board[0].length || _board[row][col] == '#') {
      return;
    }

    char letter = this._board[row][col];
    if (!parent.children.containsKey(letter)) {
      return;
    }
    TrieNode nextNode = parent.children.get(letter);
    // check if there is any match
    if (nextNode.word != null) {
      _result.add(nextNode.word);
      nextNode.word = null;
    }

    // mark the current letter before the EXPLORATION
    this._board[row][col] = '#';
    // explore neighbor cells in 4 directions: up, down, left, right
    dfs(row + 1, col, nextNode);
    dfs(row - 1, col, nextNode);
    dfs(row, col - 1, nextNode);
    dfs(row, col + 1, nextNode);

    this._board[row][col] = letter;
  }

  public static void main(String[] args) {
    WordSearchIIWithTwist a = new WordSearchIIWithTwist();
    System.out.println(a.findWords(new char[][] { { 'a' } }, new String[] { "a" }));
  }
}

class TrieNode {
  Map<Character, TrieNode> children = new HashMap<>();
  String word = null;

  public TrieNode() {
  };
}