My code:
import java.util.HashSet;
public class Solution {
private int width = 0;
private int height = 0;
public boolean exist(char[][] board, String word) {
if (board == null)
return false;
if (board.length == 0)
return false;
if (word == null || word.length() == 0)
return false;
width = board[0].length;
height = board.length;
HashSet<Integer> isVisited = new HashSet<Integer>();
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
boolean ret = helper(i, j, 0, board, word, isVisited);
if (ret)
return true;
}
}
return false;
}
private boolean helper(int i, int j, int begin, char[][] board, String word, HashSet<Integer> isVisited) {
if (!isValid(i, j, isVisited))
return false;
if (board[i][j] != word.charAt(begin))
return false;
if (begin == word.length() - 1)
return true;
isVisited.add(i * width + j);
if (helper(i - 1, j, begin + 1, board, word, isVisited))
return true;
if (helper(i + 1, j, begin + 1, board, word, isVisited))
return true;
if (helper(i, j - 1, begin + 1, board, word, isVisited))
return true;
if (helper(i, j + 1, begin + 1, board, word, isVisited))
return true;
isVisited.remove(i * width + j);
return false;
}
/**
* detect whether this location in array is valid. If it is visited, it is invalid
* @param i row
* @param j col
* @param isVisited boolean[][]
* @return whether it is valid
*/
private boolean isValid(int i, int j, HashSet<Integer> isVisited) {
if (i < 0 || i >= height)
return false;
if (j < 0 || j >= width)
return false;
return !isVisited.contains(i * width + j);
}
public static void main(String[] args) {
char[][] board = new char[3][4];
board[0][0] = 'A';
board[0][1] = 'B';
board[0][2] = 'C';
board[0][3] = 'E';
board[1][0] = 'S';
board[1][1] = 'F';
board[1][2] = 'C';
board[1][3] = 'S';
board[2][0] = 'A';
board[2][1] = 'D';
board[2][2] = 'E';
board[2][3] = 'E';
Solution test = new Solution();
System.out.println(test.exist(board, "ADFA"));
}
}
總算是過(guò)了測(cè)試完丽。一開始我是用一個(gè)，
boolean[][] isVisited 數(shù)組來(lái)做的拇舀。然后每次遞歸逻族，為了避免重復(fù)訪問(wèn)同一個(gè)元素，我都需要把原布爾數(shù)組拷貝一份傳入下層遞歸骄崩。四個(gè)方向聘鳞，上下左右，都需要拷貝一下原數(shù)組要拂。當(dāng)原數(shù)組無(wú)比巨大時(shí)抠璃，而我的每一次遞歸又都需要拷貝四次原數(shù)組，導(dǎo)致我的時(shí)間測(cè)試過(guò)不了脱惰。我在八皇后問(wèn)題中就是用這個(gè)辦法做的搏嗡，現(xiàn)在看來(lái)不是很好，或者說(shuō)拉一，很糟糕采盒。因?yàn)閿?shù)組只是很少的一部分發(fā)生了改變，但我需要重新拷貝整個(gè)數(shù)組蔚润。很像是 meng project 中的bitmap, 浪費(fèi)了大量的內(nèi)存磅氨。
然后我換用了一個(gè)HashSet<Integer>， 每次把對(duì)應(yīng)位置的i,j轉(zhuǎn)換為一個(gè)特定的index存入hash set嫡纠。
之后再刪除烦租。避免了布爾數(shù)組的問(wèn)題并且可以達(dá)到相同的效果延赌。
于是，過(guò)了測(cè)試叉橱。但是時(shí)間仍然很高挫以。
然后我看了答案。
發(fā)現(xiàn)赏迟，我的HashSet在遞歸前插入元素屡贺，遞歸后刪除元素的做法可以再簡(jiǎn)化蠢棱。
遞歸前锌杀，設(shè)置該元素為board[i][j] = '#', 因?yàn)?#不是字母，所以以后的深層遞歸是無(wú)法訪問(wèn)到他的泻仙。
遞歸后糕再，再把他改回來(lái)，不要影響其他循環(huán)下的遞歸玉转。
代碼如下：
public class Solution {
private int width = 0;
private int height = 0;
public boolean exist(char[][] board, String word) {
if (board == null)
return false;
if (board.length == 0)
return false;
if (word == null || word.length() == 0)
return false;
width = board[0].length;
height = board.length;
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
boolean ret = helper(i, j, 0, board, word);
if (ret)
return true;
}
}
return false;
}
private boolean helper(int i, int j, int begin, char[][] board, String word) {
if (i < 0 || i >= height || j < 0 || j >= width)
return false;
if (board[i][j] != word.charAt(begin))
return false;
char temp = board[i][j];
board[i][j] = '#';
if (begin == word.length() - 1)
return true;
if (helper(i - 1, j, begin + 1, board, word))
return true;
if (helper(i + 1, j, begin + 1, board, word))
return true;
if (helper(i, j - 1, begin + 1, board, word))
return true;
if (helper(i, j + 1, begin + 1, board, word))
return true;
board[i][j] = temp;
return false;
}
public static void main(String[] args) {
char[][] board = new char[3][4];
board[0][0] = 'A';
board[0][1] = 'B';
board[0][2] = 'C';
board[0][3] = 'E';
board[1][0] = 'S';
board[1][1] = 'F';
board[1][2] = 'C';
board[1][3] = 'S';
board[2][0] = 'A';
board[2][1] = 'D';
board[2][2] = 'E';
board[2][3] = 'E';
Solution test = new Solution();
System.out.println(test.exist(board, "ADFA"));
}
}
http://www.programcreek.com/2014/06/leetcode-word-search-java/
思想其實(shí)一直沒變過(guò)突想。就是dfs, 不停地往深層遞歸。就是八皇后問(wèn)題究抓。
這類問(wèn)題的統(tǒng)一思想就是猾担，
知道最終的目的是什么，確定停止條件刺下。即什么時(shí)候返回true绑嘹，不再往下遞歸。
然后橘茉，每次遞歸的時(shí)候工腋，往上下左右各個(gè)方向擴(kuò)散，并且判斷這些擴(kuò)散的方向是否有效畅卓。他們是否越界了擅腰？
他們是否之前已經(jīng)被訪問(wèn)過(guò)了。
如果判斷之前是否被訪問(wèn)過(guò)了翁潘，最簡(jiǎn)單的做法就是布爾數(shù)組趁冈，然后再每次深層遞歸時(shí)重新拷貝一份傳進(jìn)去。
但完全可以用HashSet<Integer> 來(lái)代替拜马，免去了拷貝的過(guò)程渗勘，節(jié)約了大量的時(shí)間。
然后這道題目告訴我們還可以再簡(jiǎn)化一膨。
將該元素設(shè)置為一個(gè)不滿足再次深層遞歸條件的元素呀邢。這樣，深層遞歸時(shí)再次訪問(wèn)到該元素時(shí)會(huì)自動(dòng)停止豹绪。這樣就避免了HashSet操作所帶來(lái)的消耗价淌。遞歸結(jié)束后申眼，再將該元素恢復(fù)到原來(lái)的值，避免影響其他循環(huán)中的遞歸蝉衣。
for (int i = 0; i < height; i++)
for (int j = 0; j < width; j++)
helper(...); // recursive function
**
Anyway, Good luck, Richardo!
**
My code:
public class Solution {
int row = 0;
int col = 0;
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0].length == 0 || word == null || word.length() == 0) {
return false;
}
row = board.length;
col = board[0].length;
boolean[][] isVisited = new boolean[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
isVisited[i][j] = true;
boolean flag = helper(0, word, i, j, board, isVisited);
isVisited[i][j] = false;
if (flag) {
return true;
}
}
}
return false;
}
private boolean helper(int position, String word, int i, int j, char[][] board, boolean[][] isVisited) {
if (position == word.length() - 1) {
char curr = word.charAt(position);
if (curr == board[i][j]) {
return true;
}
else {
return false;
}
}
else {
char curr = word.charAt(position);
if (curr == board[i][j]) {
if (isValid(i + 1, j) && !isVisited[i + 1][j]) {
isVisited[i + 1][j] = true;
boolean flag = helper(position + 1, word, i + 1, j, board, isVisited);
isVisited[i + 1][j] = false;
if (flag)
return flag;
}
if (isValid(i - 1, j) && !isVisited[i - 1][j]) {
isVisited[i - 1][j] = true;
boolean flag = helper(position + 1, word, i - 1, j, board, isVisited);
isVisited[i - 1][j] = false;
if (flag)
return flag;
}
if (isValid(i, j + 1) && !isVisited[i][j + 1]) {
isVisited[i][j + 1] = true;
boolean flag = helper(position + 1, word, i, j + 1, board, isVisited);
isVisited[i][j + 1] = false;
if (flag)
return flag;
}
if (isValid(i, j - 1) && !isVisited[i][j - 1]) {
isVisited[i][j - 1] = true;
boolean flag = helper(position + 1, word, i, j - 1, board, isVisited);
isVisited[i][j - 1] = false;
if (flag)
return flag;
}
return false;
}
else {
return false;
}
}
}
private boolean isValid(int i, int j) {
if (i >= 0 && i < row && j >= 0 && j < col) {
return true;
}
else {
return false;
}
}
}
這道題目就是dfs,體力活括尸。沒什么難度。
Anyway, Good luck, Richardo! -- 09/02/2016
