79. Word Search (backtracking)
Given a 2D board and a word, find if the word exists in the grid.
The word can 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.
avoid using a boolean array to store used, just set " board[i][j] = ' ' "
visited = new boolean[board.length][board[0].length];class Solution {
public boolean exist(char[][] board, String word) {
for (int i = 0 ; i < board.length; i++) {
for (int j = 0; j < board[i].length;j++) {
if (board[i][j] == word.charAt(0) && dfs(board, i, j, 0, word)) {
return true; // if find first char, and dfs search ok
}
}
}
return false;
}
private boolean dfs(char[][] board,int i, int j, int count, String word) {
if (count == word.length()) { // length equals to ori word, good!
return true;
}
if (i < 0 || i >= board.length || j < 0 || j >= board[i].length
|| board[i][j] != word.charAt(count)) {
return false; // outboud
}
char temp = board[i][j]; // backtracking
board[i][j] = ' '; // set to empty to represent used
// use or, so can't use dirs[]
boolean result =
dfs(board, i + 1, j, count+1, word) ||
dfs(board, i - 1, j, count+1, word) ||
dfs(board, i, j + 1, count+1, word) ||
dfs(board, i, j - 1, count+1, word);
board[i][j] = temp; // add back
return result;
}
}with pruning
class Solution {
private static final int[][] DIRS = {{0,1},{0,-1},{1,0},{-1,0}};
public boolean exist(char[][] grid, String word) {
if (!pruning(grid, word)) {
return false;
}
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == word.charAt(0) && dfs(grid, word, 0, i, j)) {
return true;
}
}
}
return false;
}
private boolean pruning(char[][] grid, String word) {
int m = grid.length;
int n = grid[0].length;
// pruning: case 1: not enough characters in board
if (word.length() > m * n) {
return false;
}
// pruning: case 2: board does not contain characters or enough characters that word contains
Map<Character, Integer> count = new HashMap<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int temp = count.getOrDefault(grid[i][j], 0);
count.put(grid[i][j], temp + 1);
}
}
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (!count.containsKey(c)) {
return false; // cant find word's char in hashmap
} else { // remove count one by one, because word maybe duplicate
int temp = count.get(c);
if (temp == 1) {
count.remove(c);
} else {
count.put(c, temp - 1);
}
}
}
return true;
}
private boolean dfs(char[][] grid, String word, int start, int i, int j) {
if (start == word.length()) {
return true;
}
if (!isValid(grid, i, j) || word.charAt(start) != grid[i][j]) {
return false;
}
char temp = grid[i][j];
grid[i][j] = ' ';
boolean result = false;
for (int[] dir : DIRS) {
result = dfs(grid, word, start + 1, i + dir[0], j + dir[1]);
if (result) { // find 就 break
break;
}
}
grid[i][j] = temp;
return result;
}
private boolean isValid(char[][] grid, int i, int j) {
return i >= 0 && i < grid.length && j >= 0 & j < grid[0].length;
}
}
/*
dfs search
how to ?
put first word in dfs search, then 4 direction
dfs() {
if (start == word.length()) {
return true;
}
if (4 direction) {
get result
if (not ok return false)
}
return result
}
*/new version, this is more intutive
use visited
class Solution {
private static final int[][] DIRS = {{0,1}, {0,-1}, {1,0}, {-1,0}};
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == word.charAt(0) && dfs(board, word, 0, i, j, new boolean[m][n])) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int start, int i, int j, boolean[][] visited) {
if (start == word.length()) {
return true;
}
if (!inArea(board, i, j) || visited[i][j] || word.charAt(start) != board[i][j]) {
return false;
}
visited[i][j] = true;
for (int[] dir : DIRS) {
int x = i + dir[0];
int y = j + dir[1];
if (dfs(board, word, start+1, x, y, visited)) {
return true;
}
}
visited[i][j] = false;
return false;
}
private boolean inArea(char[][] board, int x, int y) {
return x >= 0 && x < board.length && y >=0 && y < board[0].length;
}
}
/*
needs match word[0] to start
for (board)
if (ij == word[0]) {
dfs(start, i, j, )
}
retur
start == word.length
*/not use visited
以後還是寫在外面好了
class Solution {
private static final int[][] DIRS = {{0,1}, {0,-1}, {1,0}, {-1,0}};
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == word.charAt(0) && dfs(board, word, 0, i, j)) {
return true; // 為什麼都找到第一個字了, 還要傳 index 0 進去？
} // 因為 mark 是在 dfs 裡面做的, backtracking 也是
}
}
return false;
}
private boolean dfs(char[][] board, String word, int start, int i, int j) {
if (start == word.length()) {
return true;
}
if (!inArea(board, i, j) || word.charAt(start) != board[i][j]) {
return false;
}
char temp = board[i][j];
board[i][j] = ' ';
for (int[] dir : DIRS) {
int x = i + dir[0];
int y = j + dir[1];
if (dfs(board, word, start+1, x, y)) {
return true;
}
}
board[i][j] = temp;
return false;
}
private boolean inArea(char[][] board, int x, int y) {
return x >= 0 && x < board.length && y >=0 && y < board[0].length;
}
}Last updated
