Re: [閒聊] 每日LeetCode
212. Word Search II
Word Search I 的加強版本，之前是給你一個字 word 讓你檢查矩陣裡面是否存在
該單字，現在是給你大於一個的 word。
Example：
https://assets.leetcode.com/uploads/2020/11/07/search1.jpg
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"]
法一 回溯法 TLE
思路：
1.先建立一個map，記錄所有單字(a~z)是以哪些座標開頭。
2.利用回溯法遍歷 words 進 board 裡面找每個 word，如果該座標為起點找到時就提早
跳出迴圈，我們利用「#」字元來表示棋盤的位置已經被走訪過（避免回頭找）。
3.測資到倒數第二個位置的時候吃TLE。
Java Code：
-------------------------------------------
class Solution {
public List<String> findWords(char[][] board, String[] words) {
List<String> res = new ArrayList<>();
Map<Character, List<int[]>> map = new HashMap<>();
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!map.containsKey(board[i][j])) {
map.put(board[i][j], new ArrayList<>());
}
map.get(board[i][j]).add(new int[] {i, j});
}
}
boolean[][] visited = new boolean[m][n];
for (String word : words) {
if (!map.containsKey(word.charAt(0))) {
continue;
}
List<int[]> points = map.get(word.charAt(0));
for (int[] point : points) {
if (search(word, 0, board, point[1], point[0])) {
res.add(word);
break;
}
}
}
return res;
}
private boolean search(String str, int index, char[][] board, int x, int
y) {
int m = board.length;
int n = board[0].length;
if (index == str.length()) {
return true;
}
if (x < 0 || x >= n || y < 0 || y >= m) {
return false;
}
if (board[y][x] == '#' || str.charAt(index) != board[y][x]) {
return false;
}
char tmp = board[y][x];
board[y][x] = '#';
boolean flag = false;
if(search(str, index + 1, board, x + 1, y) ||
search(str, index + 1, board, x - 1, y) ||
search(str, index + 1, board, x, y + 1) ||
search(str, index + 1, board, x, y - 1)) {
flag = true;
}
board[y][x] = tmp;
return flag;
}
}
-------------------------------------------
法二 回溯法 + 字典樹
1.法一遇到 "aaaaac" "aaaaad" 這種測資時會重複DFS "aaaaa" 好幾次，我們改成不已
word的第一的單字的座標為準，而是以棋盤本身為準。
2.先把所有的 word 都加入一個字典樹，字典樹的最後一個節點放入word字串。
3.一樣用回溯法但是這次我們把棋盤上的每個點都當作起點，假設該點為(x, y)，我們對(
x, y)的上下左右進行DFS，可以走訪的條件如下：
* 座標不超出邊界
* 查找字典樹，如果存在該字元，表示當前的路徑是我們要找的，繼續DFS。
* 棋盤不可以是已經走過的(不可是#)
4.若點(x, y)滿足2的條件且當前字典樹的 word 不為 null 表示我們找到了 words 裡面
的一個單字，此時需要注意的是我們要把字典樹的該單字清掉，不然像下列的測資：
words = ["oa"]
o a b n
o t a e
a h k r
a f l v
結果會重複加到兩個oa（或者是用Set來處理也行）
4.遍歷完棋盤上的所有點之後，返回list。
--------------------------------------------
class Solution {
private char[][] board;
private List<String> result;
public List<String> findWords(char[][] board, String[] words) {
this.board = board;
this.result = new ArrayList<>();
Trie root = constructTrie(words);
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (root.children.containsKey(board[i][j])) {
backTracking(i, j, root);
}
}
}
return result;
}
private Trie constructTrie(String[] words) {
Trie root = new Trie();
for (String word : words) {
Trie node = root;
for (char c : word.toCharArray()) {
if (node.children.containsKey(c)) {
node = node.children.get(c);
} else {
Trie newNode = new Trie();
node.children.put(c, newNode);
node = newNode;
}
}
node.word = word;
}
return root;
}
private void backTracking(int y, int x, Trie root) {
if (y < 0 || x < 0 || y >= board.length || x >= board[0].length
|| board[y][x] == '#' ||
!root.children.containsKey(board[y][x])) {
return;
}
char c = board[y][x];
Trie currNode = root.children.get(c);
if (currNode.word != null) {
result.add(currNode.word);
currNode.word = null;
}
board[y][x] = '#';
backTracking(y, x + 1, currNode);
backTracking(y, x - 1, currNode);
backTracking(y + 1, x, currNode);
backTracking(y - 1, x, currNode);
board[y][x] = c;
}
}
class Trie {
Map<Character, Trie> children = new HashMap<>();
String word = null;
public Trie() {}
}
--------------------------------------------
https://i.imgur.com/j4x6moM.gif
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.159.111.108 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1667641439.A.5D9.html
※ 編輯: Rushia (49.159.111.108 臺灣), 11/05/2022 17:46:42
推
11/05 17:45,
3年前
, 1F
11/05 17:45, 1F
推
11/05 17:46,
3年前
, 2F
11/05 17:46, 2F
推
11/05 17:46,
3年前
, 3F
11/05 17:46, 3F
推
11/05 17:47,
3年前
, 4F
11/05 17:47, 4F
討論串 (同標題文章)
完整討論串 (本文為第 86 之 719 篇)：