单词搜索2

2021-01-28

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例 1：
输入：board = [
  ["o","a","a","n"],
  ["e","t","a","e"],
  ["i","h","k","r"],
  ["i","f","l","v"]],
   words = ["oath","pea","eat","rain"]
输出：["eat","oath"]

示例 2：
输入：board = [["a","b"],["c","d"]], words = ["abcb"]
输出：[]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] 是一个小写英文字母
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] 由小写英文字母组成
words 中的所有字符串互不相同
通过次数28,244提交次数63,081

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

前缀树+回溯（暴力）

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        int m = board.length;
        int n = board[0].length;
        boolean[][] road = new boolean[m][n];

        Trie root = new Trie();
        for (int i = 0; i < words.length; i++) {
            root.insert(words[i]);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                backtrack(board, road, root, i, j, new StringBuilder());
            }
        }

        return new ArrayList<>(set);
    }

    Set<String> set = new HashSet<>();


    public void backtrack(char[][] board, boolean[][] road, Trie root, int y, int x, StringBuilder bd) {
        int m = board.length;
        int n = board[0].length;
        String temp = bd.toString();
        if (root.search(temp) && !set.contains(temp)) {
            set.add(temp);
        }
        if (x < 0 || x >= n || y < 0 || y >= m || road[y][x]) return;

        bd.append(board[y][x]);
        if (root.startWith(bd.toString())) {
            road[y][x] = true;
            backtrack(board, road, root, y + 1, x, bd);
            backtrack(board, road, root, y, x + 1, bd);
            backtrack(board, road, root, y - 1, x, bd);
            backtrack(board, road, root, y, x - 1, bd);
            road[y][x] = false;
        }
        bd.deleteCharAt(bd.length() - 1);

    }

    private class Trie {
        private boolean isWord = false;
        private Trie[] next = new Trie[26];


        public Trie() {

        }

        public void insert(String word) {
            Trie root = this;
            char[] w = word.toCharArray();
            for (int i = 0; i < w.length; i++) {
                int index = w[i] - 'a';
                if (root.next[index] == null) root.next[index] = new Trie();
                root = root.next[index];
            }
            root.isWord = true;
        }

        public boolean search(String word) {
            Trie root = this;
            char[] w = word.toCharArray();
            for (int i = 0; i < w.length; i++) {
                int index = w[i] - 'a';
                if (root.next[index] == null) return false;
                root = root.next[index];
            }
            return root.isWord;
        }

        public boolean startWith(String prefix) {
            Trie root = this;
            char[] w = prefix.toCharArray();
            for (int i = 0; i < w.length; i++) {
                int index = w[i] - 'a';
                if (root.next[index] == null) return false;
                root = root.next[index];
            }
            return true;
        }
    }
}

使用前缀树的回溯

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

class Solution {
  char[][] _board = null;
  ArrayList<String> _result = new ArrayList<String>();

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

    // Step 1). Construct the Trie
    TrieNode root = new TrieNode();
    for (String word : words) {
      TrieNode node = root;

      for (Character letter : word.toCharArray()) {
        if (node.children.containsKey(letter)) {
          node = node.children.get(letter);
        } else {
          TrieNode newNode = new TrieNode();
          node.children.put(letter, newNode);
          node = newNode;
        }
      }
      node.word = word;  // store words in Trie
    }

    this._board = board;
    // Step 2). Backtracking starting for each cell in the board
    for (int row = 0; row < board.length; ++row) {
      for (int col = 0; col < board[row].length; ++col) {
        if (root.children.containsKey(board[row][col])) {
          backtracking(row, col, root);
        }
      }
    }

    return this._result;
  }
  
  private void backtracking(int row, int col, TrieNode parent) {
    Character letter = this._board[row][col];
    TrieNode currNode = parent.children.get(letter);

    // check if there is any match
    if (currNode.word != null) {
      this._result.add(currNode.word);
      currNode.word = null;
    }

    // mark the current letter before the EXPLORATION
    this._board[row][col] = '#';

    // explore neighbor cells in around-clock directions: up, right, down, left
    int[] rowOffset = {-1, 0, 1, 0};
    int[] colOffset = {0, 1, 0, -1};
    for (int i = 0; i < 4; ++i) {
      int newRow = row + rowOffset[i];
      int newCol = col + colOffset[i];
      if (newRow < 0 || newRow >= this._board.length || newCol < 0
          || newCol >= this._board[0].length) {
        continue;
      }
      if (currNode.children.containsKey(this._board[newRow][newCol])) {
        backtracking(newRow, newCol, currNode);
      }
    }

    // End of EXPLORATION, restore the original letter in the board.
    this._board[row][col] = letter;

    // Optimization: incrementally remove the leaf nodes
    if (currNode.children.isEmpty()) {
      parent.children.remove(letter);
    }
  }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/word-search-ii/solution/dan-ci-sou-suo-ii-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。