五刷 06/2022
代码跟四刷是一样的，但是四刷说终止条件可以在下一层判断我觉得是不对的
因为假如board只有一个element，就没有下一层了，这样如果丢到下一层判断就会有错
还是一样的问题，就是终止条件是在进入下一层判断还是在iterate neighbors的时候就判断
怎么写都行但是需要逻辑统一
Time O(N 3^L) -> N is the #cells of the board, 3 is the fan out factor of directions, and L is the length of the word
Space O(N + L) -> for the visited array, L (length of the word) is the depth of the stack
Runtime: 180 ms, faster than 39.18% of Java online submissions for Word Search.
Memory Usage: 42.3 MB, less than 40.58% of Java online submissions for Word Search.
class Solution {
public boolean exist(char[][] board, String word) {
// Walk to the four directions of the board, if the character matches, continue searching, otherwise return false
if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
return false;
}
boolean[][] visited = new boolean[board.length][board[0].length];
for (int y = 0; y < board.length; y++) {
for (int x = 0; x < board[0].length; x++) {
if (dfs(board, y, x, word.toCharArray(), 0, visited)) {
return true;
}
}
}
return false;
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
private boolean dfs(char[][] board, int y, int x, char[] chars, int index, boolean[][] visited) {
if (chars[index] != board[y][x]) {
return false;
}
if (index == chars.length - 1) {
return true;
}
visited[y][x] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (ny >= board.length || ny < 0 || nx >= board[0].length || nx < 0 || visited[ny][nx]) {
continue;
}
if (dfs(board, ny, nx, chars, index + 1, visited)) {
return true;
}
}
visited[y][x] = false;
return false;
}
}
Version #3 DFS with extra O(mn) space for visited boolean matrix
三刷
bug
[["a"]] "a"
一开始思路是错的，把出界条件判断和visited判断放到了进入到下一层之前
问题是如果当前正好match到最后一个char，剩下四个方向全部invalid，还是需要进到下一层进行判断然后return true
所以把所有条件判断都放到了下一层
然后发现。。。。和二刷犯的错一模一样。。。
70.29 %
class Solution {
public boolean exist(char[][] board, String word) {
if (word == null || board == null || board.length == 0
|| board[0] == null || board[0].length == 0) {
return false;
}
boolean[][] visited = new boolean[board.length][board[0].length];
for (int y = 0; y < board.length; y++) {
for (int x = 0; x < board[0].length; x++) {
if (dfs(board, x, y, word, 0, visited)) {
return true;
}
}
}
return false;
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
private boolean dfs(char[][] board, int x, int y, String word, int index, boolean[][] visited) {
if (index == word.length()) { // all chars are matched
return true;
}
if (y < 0 || y >= board.length || x < 0 || x >= board[0].length
|| visited[y][x] || board[y][x] != word.charAt(index)) {
return false;
}
// current char matched
visited[y][x] = true;
for (int i = 0; i < 4; i++) { // search for 4 directions
// new y -> y + dy[i], new x -> x + dx[i]
int nextY = y + dy[i];
int nextX = x + dx[i];
// in bound
if (dfs(board, nextX, nextY, word, index + 1, visited)) {
return true;
}
}
// backtracking
visited[y][x] = false;
return false;
}
}
二刷
感觉反而不如上一次写的好了
这里的success的base case最开始写成了index == word.length()也就是说在最后一个字母的下一层判断，这样有一个问题，就是matrix没有其他地方可走的时候，即使已经匹配到了最后，也没法返回true
而且效率有些浪费
新方法是说直接看neighbor的char和目标等不等，如果不相等就直接不进入recursion
version#2 写的是进入recursion之后判断一下等不等，然后再index == word.length() - 1就返回
这两个思路差的不多，但是都一定要事先想清楚
还是version #2 比较好其实，冗余的代码比较少
不过version #3可以节省一些stack的空间 因为这里只有4叉树无所谓，如果分叉比较多的时候3比较好
Submission Result: Wrong Answer More Details
public class Solution {
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0] == null || board[0].length == 0 || word == null || word.length() == 0) throw new IllegalArgumentException();
int rows = board.length;
int cols = board[0].length;
boolean[][] visited = new boolean[rows][cols];
for (int x = 0; x < rows; x++) {
for (int y = 0; y < cols; y++) {
if (board[x][y] == word.charAt(0) && existDfsHelper(new int[] {x, y}, 0, board, word, visited)) return true;
}
}
return false;
}
//base case: found(index == word.lengt())-return true
//if current character equals to the character at the given index
//traverse neighbors
private int[] dx = {1, 0, -1, 0};
private int[] dy = {0, 1, 0, -1};
//x = xy[0], y = xy[1]
private boolean existDfsHelper(int[] xy, int index, char[][] board, String word, boolean[][] visited) {
if (index == word.length() - 1) return true;
//neighbor's position
int nx = 0, ny = 0;
visited[xy[0]][xy[1]] = true;
for (int i = 0; i < 4; i++) {
nx = xy[0] + dx[i];
ny = xy[1] + dy[i];
if (nx >= 0 && nx < board.length && ny >= 0 && ny < board[0].length && !visited[nx][ny]) {
if (board[nx][ny] == word.charAt(index + 1) && existDfsHelper(new int[] {nx, ny}, index + 1, board, word, visited)) {
return true;
}
}
}
visited[xy[0]][xy[1]] = false;
return false;
}
}
Version #2 DFS and check visited by marking the visited board with '0' null
ASCII number of 0 represents null
92.69%
public class Solution {
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0] == null || board[0].length == 0 || word.length() == 0) return false;
int rows = board.length, cols = board[0].length;
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (dfs(board, row, col, word, 0)) return true;
}
}
return false;
}
private int[] dx = {1, 0, -1, 0};
private int[] dy = {0, 1, 0, -1};
private boolean dfs(char[][] board, int x, int y, String word, int index) {
//Base case
if (board[x][y] != word.charAt(index)) return false;
if (index == word.length() - 1) return true;
char currChar = board[x][y];
board[x][y] = 0;
for (int i = 0; i < 4; i++) {
if (isValid(board.length, board[0].length, x + dx[i], y + dy[i]) && board[x + dx[i]][y + dy[i]] != 0) {
if (dfs(board, x + dx[i], y + dy[i], word, index + 1)) return true;
}
}
//Backtracking -> reset the current character
board[x][y] = currChar;
return false;
}
private boolean isValid(int cows, int cols, int x, int y) {
return x >= 0 && x < cows && y >= 0 && y < cols;
}
}
四刷 05/21/2021
跟前面几次犯的错误都一模一样，摔倒在了["a"] "a"这个case上面
这里有一个比较不常见的判断是到了下一层再判断是不是出界，而不是平时经常用的， 出界就不进入
这个是个灵活运用的点
Runtime: 98 ms, faster than 22.43% of Java online submissions for Word Search.
Memory Usage: 36.6 MB, less than 88.07% of Java online submissions for Word Search.
class Solution {
public boolean exist(char[][] board, String word) {
for (int y = 0; y < board.length; y++) {
for (int x = 0; x < board[0].length; x++) {
if (helper(y, x, board, word, 0)) {
return true;
}
}
}
return false;
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
// Check if current grid matches given character.
private boolean helper(int y, int x, char[][] board, String word, int index) {
if (index == word.length()) {
return true;
}
if (x < 0 || x >= board[0].length || y < 0 || y >= board.length || word.charAt(index) != board[y][x]) {
return false;
}
char c = board[y][x];
// System.out.println("board->" + c);
board[y][x] = '#';
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (helper(ny, nx, board, word, index + 1)) {
// no need to reset since the whole process will be terminated
return true;
}
}
// reset
board[y][x] = c;
return false;
}
}
Version #1 DFS with self-defined hash function
8.17%
public class Solution {
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0] == null || board[0].length == 0 || word.length() == 0) return false;
int rows = board.length, cols = board[0].length;
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (dfs(board, row, col, word, 0)) return true;
}
}
return false;
}
private int[] dx = {1, 0, -1, 0};
private int[] dy = {0, 1, 0, -1};
private Set<Integer> visited = new HashSet<>();
private boolean dfs(char[][] board, int x, int y, String word, int index) {
//Base case
if (board[x][y] != word.charAt(index)) return false;
if (index == word.length() - 1) return true;
Integer hash = x * board[0].length + y;
visited.add(hash);
for (int i = 0; i < 4; i++) {
if (isValid(board.length, board[0].length, x + dx[i], y + dy[i]) && !visited.contains(hash + dx[i] * board[0].length + dy[i])) {
if (dfs(board, x + dx[i], y + dy[i], word, index + 1)) return true;
}
}
visited.remove(hash);
return false;
}
private boolean isValid(int cows, int cols, int x, int y) {
return x >= 0 && x < cows && y >= 0 && y < cols;
}
}
No comments:
Post a Comment