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


  • 3
    S

    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;
                            x_pos.add(i);y_pos.add(j);
                            word_index.add(0);
                            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;
                                x_track.add(x);y_track.add(y);
                                visited[x][y] = true;
                                if(x-1 >= 0){
                                    if(board[x-1][y] == word.charAt(index) && !visited[x-1][y]){
                                        x_pos.add(x-1);y_pos.add(y);
                                        word_index.add(index);
                                        count_subpath++;
                                    }
                                }
                                if(x+1 < board.length){
                                    if(board[x+1][y] == word.charAt(index) && !visited[x+1][y]){
                                        x_pos.add(x+1);y_pos.add(y);
                                        word_index.add(index);
                                        count_subpath++;
                                    }
                                }
                                if(y-1 >= 0){
                                    if(board[x][y-1] == word.charAt(index) && !visited[x][y-1]){
                                        x_pos.add(x);y_pos.add(y-1);
                                        word_index.add(index);
                                        count_subpath++;
                                    }
                                }
                                if(y+1 < board[0].length){
                                    if(board[x][y+1] == word.charAt(index) && !visited[x][y+1]){
                                        x_pos.add(x);y_pos.add(y+1);
                                        word_index.add(index);
                                        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;
            }
        }

  • 0
    R

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


  • 0
    S

    You are right.


  • 0
    C

    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;
        }
    }
    

Log in to reply
 

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