# My Java Accepted Solution using Iterative Method (no recursive call)

• I saw a lot dfs recursive version. I happen to do it in a iterative way. Share my solution with you.
Notice: Need to trace back and reset visited from true->false once a wrong end encountered.

``````public class Solution {
public boolean exist(char[][] board, String word) {
for(int i = 0;i < board.length;i++){
for(int j = 0;j < board[0].length;j++){
if(board[i][j] == word.charAt(0)){
// dfs
Stack<Integer> x_pos = new Stack<Integer>();
Stack<Integer> y_pos = new Stack<Integer>();
Stack<Integer> word_index = new Stack<Integer>();
Stack<Integer> x_track = new Stack<Integer>();
Stack<Integer> y_track = new Stack<Integer>();
int[][] subpath_num = new int[board.length][board[0].length];
boolean[][] visited = new boolean[board.length][board[0].length];
for(int q = 0;q < board.length;q++)
for(int p = 0;p < board[0].length;p++)
visited[q][p] = false;
while(!x_pos.isEmpty()){
int x = x_pos.pop();
int y = y_pos.pop();
int index = word_index.pop()+1;
if(index == word.length()){return true;}
int count_subpath = 0;
visited[x][y] = true;
if(x-1 >= 0){
if(board[x-1][y] == word.charAt(index) && !visited[x-1][y]){
count_subpath++;
}
}
if(x+1 < board.length){
if(board[x+1][y] == word.charAt(index) && !visited[x+1][y]){
count_subpath++;
}
}
if(y-1 >= 0){
if(board[x][y-1] == word.charAt(index) && !visited[x][y-1]){
count_subpath++;
}
}
if(y+1 < board[0].length){
if(board[x][y+1] == word.charAt(index) && !visited[x][y+1]){
count_subpath++;
}
}
subpath_num[x][y] = count_subpath;
// reset the visited mark
if(subpath_num[x][y] == 0){
int cur_x = x_track.pop();
int cur_y = y_track.pop();
while(subpath_num[cur_x][cur_y] <= 1){
visited[cur_x][cur_y] = false;
if(x_track.isEmpty()){break;}
cur_x = x_track.pop();
cur_y = y_track.pop();
}
subpath_num[cur_x][cur_y]--;
}
}
}
}
}
return false;
}
}``````

• it's not necessary to initialize boolean visited[][], its elements are false by default.

• You are right.

• made some modifications to have it passed a naughty test case.

``````public class Solution {

public boolean exist(char[][] board, String word) {
if (board == null || word == null) {
return false;
}

int rowLen = board.length,
colLen = board[0].length,
wordLen = word.length();

if (rowLen * colLen < wordLen) {
return false;
}

Stack<int[]> params = new Stack<>(); // {row, col, pointer}
int[][] subCount = new int[rowLen][colLen];
boolean[][] visited = new boolean[rowLen][colLen];

for (int i = 0; i < rowLen; i++) {
for (int j = 0; j < colLen; j++) {
if (board[i][j] == word.charAt(0)) {
params.push(new int[]{i, j, 0});
while (!params.isEmpty()) {
int pointer = params.peek()[2] + 1;
if (pointer >= word.length()) {
return true;
}

int row = params.peek()[0], col = params.peek()[1];
visited[row][col] = true;
if (subCount[row][col] != 0) {
params.pop();
visited[row][col] = false;
subCount[row][col] = 0;
continue;
}

int entries = 0;
int[] rows = new int[]{row - 1, row + 1},
cols = new int[]{col - 1, col + 1};

for (int currRow : rows) {
if (currRow >= 0 && currRow < rowLen && !visited[currRow][col] && board[currRow][col] == word.charAt(pointer)) {
params.push(new int[]{currRow, col, pointer});
entries++;
}
}
for (int currCol : cols) {
if (currCol >= 0 && currCol < colLen && !visited[row][currCol] && board[row][currCol] == word.charAt(pointer)) {
params.push(new int[]{row, currCol, pointer});
entries++;
}
}
if (entries == 0) {
params.pop();
visited[row][col] = false;
}

subCount[row][col] = entries;
}
}
}
}
return false;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.