LeetCode 212. 单词搜索 II

朱雀 2022-10-29 14:23 4阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70 1]  
[官方][Link 1]

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/1865d422357d4bc49c0048589624c3e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70 1]: /images/20221024/d684ad9398d644e9a91838877a5f4974.png
[Link 1]: https://leetcode-cn.com/problems/word-search-ii/solution/dan-ci-sou-suo-ii-by-leetcode/