leetcode算法练习【212】*单词搜索 II

深碍√TFBOYSˉ_ 2023-02-11 13:27 15阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：暴力回溯，给过了~
             *   *  复杂度计算
             *  方案2：前缀树
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。
    
    单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
    
    示例:
    
    输入: 
    words = ["oath","pea","eat","rain"] and board =
    [
      ['o','a','a','n'],
      ['e','t','a','e'],
      ['i','h','k','r'],
      ['i','f','l','v']
    ]
    
    输出: ["eat","oath"]
    说明:
    你可以假设所有输入都由小写字母 a-z 组成。
    
    提示:
    
    你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？
    如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题： 实现Trie（前缀树）。

#### 方案：暴力回溯，给过了~ ####

class Solution { 
            private int[][] tmp;
            private char[][] board;
            private String word;
            private int row;
            private int col;
            LinkedList<String> output = new LinkedList<>();
    
            public List<String> findWords(char[][] board, String[] words) { 
    
                this.row = board.length;
                if (this.row < 1)
                    return output;
                this.col = board[0].length;
    
                this.board = board;
                // 从每格开始当头匹配
                loop1: for (int k = 0; k < words.length; k++) { 
                    this.word = words[k];
                    tmp = new int[row][col];
                    for (int i = 0; i < row; i++) { 
                        for (int j = 0; j < col; j++) { 
                            // 如果找到了，那么就进入下一个循环
                            if (backtrack(i, j, 0))
                                continue loop1;
                        }
                    }
                }
                return output;
            }
    
            public boolean backtrack(int i, int j, int k) { 
    
                if (board[i][j] == word.charAt(k)) { 
                    if (k == word.length() - 1) { 
                        output.add(word);
                        return true;
                    }
                    // next turn 上下左右寻找
                    tmp[i][j] = 1;
                    if (i > 0 && tmp[i - 1][j] == 0 && backtrack(i - 1, j, k + 1)) { 
                        return true;
                    } else if (i < row - 1 && tmp[i + 1][j] == 0 && backtrack(i + 1, j, k + 1)) { 
                        return true;
                    } else if (j > 0 && tmp[i][j - 1] == 0 && backtrack(i, j - 1, k + 1)) { 
                        return true;
                    } else if (j < col - 1 && tmp[i][j + 1] == 0 && backtrack(i, j + 1, k + 1)) { 
                        return true;
                    }
                    tmp[i][j] = 0;
                }
                return false;
            }
        }

##### 复杂度计算 #####

*  时间复杂度：O(mnsk),mn数组长宽，s是String数组长度，k每个String的长度（可能不同，取平均吧）
 *  空间复杂度：O(n)

#### 方案2：前缀树 ####

*  1中是取一个单词查看矩阵里是否有解，2中是遍历一遍矩阵，看是否包含单词

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

##### 复杂度计算 #####

*  时间复杂度：( O ( M ( 4 ⋅ 3 L − 1 ) ) O ( M ( 4 ⋅ 3 L − 1 ) ) \\mathcal\{O\}(M(4\\cdot3^\{L-1\}))O(M(4⋅3 L−1)) O(M(4⋅3L−1))O(M(4⋅3L−1)))
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode