212.Word-Search-II

212. Word Search II

题目地址

https://leetcode.com/problems/word-search-ii/solution/

题目描述

Given a 2D board and a list of words from the dictionary, find all words in the board.

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

Example:
Input: 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

代码

Approach #1 Backtracking with Trie

class Solution {

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

  char[][] board;
  int[] dr = new int[] {0, 1, -1, 0};
  int[] dc = new int[] {1, 0, 0, -1};
  public List<String> findWords(char[][] board, String[] words) {
    TrieNode root = new TrieNode();
    this.board = board;
    for (String word: words) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            if (node.children.containsKey(word.charAt(i))) {
                node = node.children.get(word.charAt(i));
            } else {
                TrieNode newNode = new TrieNode();
                node.children.put(word.charAt(i), newNode);
                node = newNode;
            }
        }
        node.word = word;
    }

    List<String> ans = new ArrayList();
    for (int r = 0; r < board.length; r++) {
      for (int c = 0; c < board[0].length; c++) {
        if (root.children.containsKey(board[r][c])) {
            dfs(ans, root, r, c);
        }
      }
    }
    return ans;
}

    private void dfs(List<String> ans, TrieNode parent, int row, int col) {
    Character letter = board[row][col];
    TrieNode currNode = parent.children.get(letter);

    if (currNode.word != null) {
      ans.add(currNode.word);
      currNode.word = null;
    } 

    board[row][col] = '#';
    for (int i = 0; i < 4; ++i) {
      int newRow = row + dr[i];
      int newCol = col + dc[i];
      if (newRow >= 0 && newRow < board.length && newCol >= 0
        && newCol < board[0].length && 
          currNode.children.containsKey(board[newRow][newCol])) {
          dfs(ans, currNode, newRow, newCol);
      }
    }
    board[row][col] = letter;

    }
}