Related: LeetCode 212 - Word Search II
[LeetCode124]Word Search - coder 进阶的专栏 - 博客频道 - CSDN.NET
word =
word =
The idea of this question is as follows:
(1) Find the 1st element of the word in the board.
(2) For each position found where the 1st element lies, recursively do:
(i) Search the around cell to see if the next element exists. (4 directions: (i-1,j),(i+1,j),(i,j-1),(i,j+1) )
(ii) If the word ends, return true.
(3) Return false if no matching found.
Note: A visited matrix is needed to store the positions where have already been visited. Details can be found in code.
but when your algorithm is running, board[][] is changed, which prevents it from concurrent usage.
we have O(mn) for each for loop, then we search the whole elements again, which is O(mn) in total it is O(m^2n^2) time complexity
I think the space complexity is
https://discuss.leetcode.com/topic/37162/what-is-the-time-complexity-for-the-dfs-solution
X. Using visited[][]
https://discuss.leetcode.com/topic/21142/my-java-solution
https://github.com/zhongjianluxian/LeetCode/blob/master/src/LeetCode/WordSearch.java
http://www.lifeincode.net/programming/leetcode-word-search-java/
http://www.jiuzhang.com/solutions/word-search/
X. Using origin input as visited[]
https://discuss.leetcode.com/topic/7907/accepted-very-short-java-solution-no-additional-space/39
https://segmentfault.com/a/1190000003697153
这道题其实还可以变一变，比如字符可以重复使用。准备的时候多联想还是比较好的，因为面试中常常会做完一道题会变一下问问，虽然经常不用重新写代码，但是想了解一下思路.
Word Search Problem - Non-recursive Solution
http://www.bo-yang.net/2014/07/28/word-search/
C code:
http://algorithmsgeek.blogspot.com/2013/07/algo47-word-search-in-matrix-of-nn.html
Looks too complicated.
https://discuss.leetcode.com/topic/45252/java-dfs-solution-beats-97-64
Read full article from [LeetCode124]Word Search - coder 进阶的专栏 - 博客频道 - CSDN.NET
[LeetCode124]Word Search - coder 进阶的专栏 - 博客频道 - CSDN.NET
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.
For example,
Given board =
Given board =
[ ["ABCE"],
["SFCS"],
["ADEE"] ]word =
"ABCCED", -> returns true,word =
"SEE", -> returns true,word =
"ABCB", -> returns false.The idea of this question is as follows:
(1) Find the 1st element of the word in the board.
(2) For each position found where the 1st element lies, recursively do:
(i) Search the around cell to see if the next element exists. (4 directions: (i-1,j),(i+1,j),(i,j-1),(i,j+1) )
(ii) If the word ends, return true.
(3) Return false if no matching found.
Note: A visited matrix is needed to store the positions where have already been visited. Details can be found in code.
but when your algorithm is running, board[][] is changed, which prevents it from concurrent usage.
we have O(mn) for each for loop, then we search the whole elements again, which is O(mn) in total it is O(m^2n^2) time complexity
I think the space complexity is
O(4mn) if the function call stack is taken into account. In each cell, we recursively call its 4four neighbors and there are mn cells in total.https://discuss.leetcode.com/topic/37162/what-is-the-time-complexity-for-the-dfs-solution
X. Using visited[][]
https://discuss.leetcode.com/topic/21142/my-java-solution
https://github.com/zhongjianluxian/LeetCode/blob/master/src/LeetCode/WordSearch.java
http://www.lifeincode.net/programming/leetcode-word-search-java/
http://www.jiuzhang.com/solutions/word-search/
Use visited array.
https://leetcode.com/discuss/23165/accepted-very-short-java-solution-no-additional-space
boolean[][] visited;
public boolean exist(char[][] board, String word) {
if (word.length() == 0)
return true;
int m = board.length;
int n = board[0].length;
visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (search(board, word, 0, i, j))
return true;
}
}
return false;
}
private boolean search(char[][] board, String word, int n, int i, int j) {
if (n == word.length())
return true;
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length)
return false;
if (visited[i][j])
return false;
if (word.charAt(n) != board[i][j])
return false;
visited[i][j] = true;
boolean result = search(board, word, n + 1, i - 1, j)
|| search(board, word, n + 1, i + 1, j) || search(board, word, n + 1, i, j - 1)
|| search(board, word, n + 1, i, j + 1);
|| search(board, word, n + 1, i + 1, j) || search(board, word, n + 1, i, j - 1)
|| search(board, word, n + 1, i, j + 1);
visited[i][j] = false;
return result;
}
http://www.programcreek.com/2014/06/leetcode-word-search-java/https://leetcode.com/discuss/23165/accepted-very-short-java-solution-no-additional-space
My java code use similar idea. restriction is '*' cannot be present in the input char matrix.
public boolean exist(char[][] board, String word) { int m = board.length; int n = board[0].length; boolean result = false; for(int i=0; i<m; i++){ for(int j=0; j<n; j++){ if(dfs(board,word,i,j,0)){ result = true; // break here return true; } } } return result; } public boolean dfs(char[][] board, String word, int i, int j, int k){ int m = board.length; int n = board[0].length; if(i<0 || j<0 || i>=m || j>=n){ // its easier, put check here return false; } if(board[i][j] == word.charAt(k)){ char temp = board[i][j]; board[i][j]='#'; // modified original array, use it as visited array if(k==word.length()-1){ return true; }else if(dfs(board, word, i-1, j, k+1) ||dfs(board, word, i+1, j, k+1) ||dfs(board, word, i, j-1, k+1) ||dfs(board, word, i, j+1, k+1)){ return true; } board[i][j]=temp; } return false; } |
X. Using origin input as visited[]
https://discuss.leetcode.com/topic/7907/accepted-very-short-java-solution-no-additional-space/39
public boolean exist(char[][] board, String word) {
char[] wordArray = word.toCharArray();
int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(dfs(board, dirs, i, j, wordArray, 0)) return true;
}
}
return false;
}
public boolean dfs(char[][] board, int[][] dirs, int i, int j, char[] word, int start) {
if(start == word.length) return true;
if(i < 0 || j < 0 || i == board.length || j == board[0].length) return false;
if(board[i][j] == '#' || board[i][j] != word[start]) return false;
char c = board[i][j];
board[i][j] = '#'; // use '#' to represent this cell is visited
for(int[] dir: dirs) {
int newRow = i + dir[0], newCol = j + dir[1];
if(dfs(board, dirs, newRow, newCol, word, start + 1)) return true
}
board[i][j] = c; // backtracking
return false;
}
}https://segmentfault.com/a/1190000003697153
基本思路很简单，对矩阵里每个点都进行一次深度优先搜索，看它能够产生一个路径和所给的字符串是一样的。重点在如何优化搜索，避免不必要的计算。比如我们一个方向的搜索中已经发现了这个词，那我们就不用再搜索。另外，为了避免循环搜索，我们还要将本轮深度优先搜索中搜索过的数字变一下，等递归回来之后再变回来。实现这个特性最简单的方法就是异或上一个特定数，然后再异或回来。
public boolean exist(char[][] board, String word) {
if(board.length == 0) return false;
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
// 从i,j点作为起点开始搜索
boolean isExisted = search(board, i, j, word, 0);
if(isExisted) return true;
}
}
return false;
}
private boolean search(char[][] board, int i, int j, String word, int idx){
if(idx >= word.length()) return true;
if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(idx)) return false;
// 将已经搜索过的字母标记一下，防止循环。只要变成另外一个字符，就不会再有循环了。
board[i][j] ^= 255;
boolean res = search(board, i-1, j, word, idx+1) || search(board, i+1, j, word, idx+1) || search(board, i, j-1, word, idx+1) || search(board, i, j+1, word, idx+1);
// 再次异或255就能恢复成原来的字母
board[i][j] ^= 255;
return res;
}public class Solution {
int[][] visited;
public boolean exist(char[][] board, String word) {
if(word.length()==0) return false;
if(board.length==0 || board[0].length==0) return false;
int row = board.length;
int col = board[0].length;
visited = new int [row][col];
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(board[i][j] == word.charAt(0)){
visited[i][j] = 1;
if(search(board, word, -1, i, j, 1))
return true;
visited[i][j] = 0;
}
}
}
return false;
}
//op 0123 up down left right
public boolean search(char[][] board, String word,int op,int i, int j, int matchLen){
if(matchLen == word.length()) return true;
int row = board.length;
int col = board[0].length;
if(i+1<row && op!=0){//down
if(visited[i+1][j]==0 && board[i+1][j]==word.charAt(matchLen)){
visited[i+1][j] =1;
if(search(board, word, 1, i+1, j, matchLen+1))
return true;
visited[i+1][j]=0;
}
}
if(i-1>=0 && op!=1){//up
if(visited[i-1][j]==0 && board[i-1][j] == word.charAt(matchLen)){
visited[i-1][j] = 1;
if(search(board, word, 0, i-1, j, matchLen+1))
return true;
visited[i-1][j] = 0;
}
}
if(j+1<col && op!=2){
if(visited[i][j+1] ==0 && board[i][j+1] == word.charAt(matchLen)){
visited[i][j+1] = 1;
if(search(board, word, 3, i, j+1, matchLen+1))
return true;
visited[i][j+1] = 0;
}
}
if(j-1>=0 && op!=3){
if(visited[i][j-1] ==0 && board[i][j-1] == word.charAt(matchLen)){
visited[i][j-1] = 1;
if(search(board, word, 2, i, j-1, matchLen+1))
return true;
visited[i][j-1] = 0;
}
}
return false;
}
}
这道题其实还可以变一变，比如字符可以重复使用。准备的时候多联想还是比较好的，因为面试中常常会做完一道题会变一下问问，虽然经常不用重新写代码，但是想了解一下思路.
Word Search Problem - Non-recursive Solution
http://www.bo-yang.net/2014/07/28/word-search/
C code:
http://algorithmsgeek.blogspot.com/2013/07/algo47-word-search-in-matrix-of-nn.html
Looks too complicated.
/* A recursive utility function to solve search problem in all 8 side (including diagonal sides) */ |
037 | int search_rec(char arr[][N], int currrow, int currcol,int**used,char *str,int len,int index) |
038 | { |
039 | int i,j,ret=0; |
040 |
041 | // CASE 1: when going beyond last char to search |
042 | if(index == len) |
043 | { |
044 | printMatrix(used); |
045 | return true;//solve successfully |
046 | } |
047 |
048 | //CASE 2: out-of-bound check |
049 | if(!isValidIndexes(currrow,currcol)) |
050 | { |
051 | return false; |
052 | } |
053 |
054 | //CASE 3 : if we encounter already used cell, NOT ALLOWD , so return false |
055 | if(used[currrow][currcol] == 1 ) |
056 | { |
057 | return false; |
058 | } |
059 | //CASE 4 : CRITICAL ... WE CAN ONLY GO FOR 8 NEIGHBOUR SEARCH , ONCE WE FOUND FIRST INDEX |
060 | if(arr[currrow][currcol]!=str[index] && index ==0) //for 0th index search |
061 | { |
062 | //CASE 4.1 : search same index on same row for next col |
063 | if(currcol != N-1) |
064 | returnsearch_rec(arr,currrow,currcol+1,used,str,len,index);//right adjecent element |
065 | //CASE 4.2 : search same index on next row staring from zero col |
066 | else if(currrow != N-1) |
067 | return search_rec(arr,currrow+1,0,used,str,len,index);//next row element |
068 | //CASE 4.3 : 0th index itself not exist any where |
069 | else |
070 | return false; |
071 | } |
072 |
073 | //CASE 5 : check for current element match current index of str |
074 | if(arr[currrow][currcol] == str[index]) |
075 | { |
076 | used[currrow][currcol] = 1; //marking as used match |
077 | //CASE 5.1: index match, so now try all possible remaining 8 neighbours |
078 |
079 | ret = search_rec(arr,currrow,currcol-1,used,str,len,index+1)//left adjecent element |
080 | || search_rec(arr,currrow,currcol+1,used,str,len,index+1)//right adjecent element |
081 | || search_rec(arr,currrow-1,currcol,used,str,len,index+1)//upper adjecent element |
082 | || search_rec(arr,currrow+1,currcol,used,str,len,index+1)//lower adjecent element |
083 | || search_rec(arr,currrow+1,currcol-1,used,str,len,index+1)//left-lower diagonal element |
084 | || search_rec(arr,currrow+1,currcol+1,used,str,len,index+1)//right-lower diagonal element |
085 | || search_rec(arr,currrow-1,currcol-1,used,str,len,index+1)//left-upper diagonal element |
086 | || search_rec(arr,currrow-1,currcol+1,used,str,len,index+1);//right-upperdiagonal element |
087 |
088 | used[currrow][currcol] = 0; //reset again... backtrack |
089 |
090 | return ret; // it will be true if next index found in any of 8 adjecent element |
091 |
092 | } |
093 | else |
094 | { |
095 | //CASE 5.2: index doen't match |
096 | return false; |
097 | } |
098 |
099 | } |
100 |
101 | void searchstr(char arr[N][N],int row,int col, char *str,int len) |
102 | { |
103 | // we need to maintain which element are (1) taken and (2) which element we are not taken |
104 | // all these detail can be maintain in USED array of same size |
105 |
106 | int **used = (int **)malloc(sizeof(int *) * N); |
107 |
108 | int i,j; |
109 |
110 | for(i=0;i<N;i++) |
111 | { |
112 | used[i] = (int *)malloc(sizeof(int) * N); |
113 | for(j=0;j<N;j++) |
114 | { |
115 | used[i][j] = 0; |
116 | } |
117 | } |
118 | int start_index=0; |
119 |
120 | //initial call would start from 0,0 |
121 | if(search_rec(arr,0,0,used,str,len,start_index)) |
122 | { |
123 | printf("\nWord [%s] found.\n",str); |
124 | } |
125 | else |
126 | { |
127 | printf("\nWord [%s] not found.\n",str); |
128 | } |
129 |
130 | //free allocated memory |
131 | for(i=0;i<N;i++) |
132 | { |
133 | free(used[i]); |
134 | } |
135 | free(used); |
136 | } |
Read full article from [LeetCode124]Word Search - coder 进阶的专栏 - 博客频道 - CSDN.NET
