为什么在下面给出的WordSearch问题中使用Trie数据结构？

Question

给出了一个m字符板和一个字符串单词列表，返回板上的所有单词.

每个单词必须由顺序相邻单元的字母构成，其中相邻单元是水平或垂直相邻的。同一字母单元格不能在一个单词中使用超过一次。

词搜索问题

Answer 1

布鲁特力方法:时间复杂度为O(num )。*M*4* 3^L-1)

1. M=二维矩阵中的单元格数
2. L=单词最大长度的长度。

    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的方法

1. 时间复杂度降低到O(M *4* 3^L-1)
2. 引入对空间O(2N)的需要；在最坏的情况下，Trie将有与所有单词的字母相同的节点，其中N是字母的总数。因为我们还存储要搜索的字符串N变为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() {
  };
}

Answer 2

下面是一种具有增强型节点结构的替代解决方案，它使代码更简单。

我将由你来决定哪个更适合你的需要：

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 3

您可能想使用Trie的原因是您可以使用TRIE来索引整个板(尽管创建这个trie并不简单)，在创建trie之后，您可以在O(1)时间内找到它中的任何单词。

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*

初始化后，您可以丢弃板和字典，以后的任何查找都将非常快，内存开销也很低。

想要这样做的一个原因可能是，您希望将游戏中的开销降到最低，并且可以选择预编译开发中的“游戏”，并将“编译”trie发送到产品中。