Why's this answer LTE


  • 0
    H

    Logically this is quite similar to several existing answers. How can I modify it to make it an AC...
    Thanks very much for help and advise.

       public class Solution {
            public boolean exist(char[][] board, String word) {
                int m = board.length, n = board[0].length;
                char ch = word.charAt(0);
            
            for( int i = 0; i<m; i++){
                for(int j = 0; j<n; j++){
                    if(board[i][j] == ch)
                        board[i][j] = 0;
                        if( find(i, j, board, word,1))
                            return true;
                        board[i][j] = ch;
                }
            }
            return false;
        }
        
        public boolean find(int x, int y, char[][] board, String word, int pos){
            if(word.length()<=pos) return true;
            if(x<0 || x >=board.length || y < 0 || y >=board[0].length) return false;
            char ch = word.charAt(pos);
            if(board[x][y] == ch) {
                board[x][y] = 0;
                if( find(x-1, y, board,  word, pos+1) || find(x+1, y, board,  word, pos+1) || find(x, y-1, board,  word, pos+1) || find(x, y+1, board,  word, pos+1))
                    return true;
                board[x][y] = ch;
            }
            return false;
        }
    }

  • 0
    B

    I made some modifications on your code. It will ac and beats 80 %.

    public class Solution {
        public boolean exist(char[][] board, String word) {
            int m = board.length, n = board[0].length;
            char ch = word.charAt(0);
    
            for( int i = 0; i<m; i++){
                for(int j = 0; j<n; j++){
                    if(board[i][j] == ch) {
                        //board[i][j] = 0;
                        if(find(i, j, board, word,0)) return true;
                        //board[i][j] = ch;
                    }
                }
            }
            return false;
        }
    
        public boolean find(int x, int y, char[][] board, String word, int pos){
            if(word.length()<=pos) return true;
            if(x<0 || x >=board.length || y < 0 || y >=board[0].length) return false;
            char ch = word.charAt(pos);
            if(board[x][y] == ch) {
                board[x][y] = 0;
                if( find(x-1, y, board,  word, pos+1) || find(x+1, y, board,  word, pos+1) || find(x, y-1, board,  word, pos+1) || find(x, y+1, board,  word, pos+1))
                    return true;
                board[x][y] = ch;
            }
            return false;
        }
    }

  • 0
    H

    Thanks sooo much.

    But why does this change can make it.
    How much does //board[i][j] = 0; cost in exist()?


  • 0
    B

    All the backtracing logic is handled in your find method


Log in to reply
 

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