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

问题描述 投票:0回答:4

给定一个 m x n 的字符板和一个字符串单词列表,返回板上的所有单词。

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

单词搜索问题

java graph-algorithm depth-first-search trie recursive-backtracking
4个回答
1
投票

蛮力方法:时间复杂度将为O(词数 * M * 4 * 3^L-1)

  1. M = 2D 矩阵中的单元数
  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;
      }
    }

基于字典树的方法

  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() {
  };
}

1
投票

这是一种替代解决方案,具有增强的节点结构,使代码更简单。
我将由您决定哪个更适合您的需求:

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 ;
    }
}

1
投票

您可能想要使用 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 发送到生产环境


0
投票

单词搜索1:在网格中搜索一个单词。

单词搜索需要从每个单元格开始查找单词。

优化1:利用回溯提前终止无效搜索。

单词搜索2:在网格中搜索多个单词。

对于每个单词,应用回溯。

优化2:一次解析,一次性查找所有单词。在每个单元格中,trie 帮助找出是否有任何单词匹配。

© www.soinside.com 2019 - 2024. All rights reserved.