Java 6-8ms beats 97-99%, though I don't know why


  • 0
    S

    Could anyone explain? 0- 0

    public class Solution {
        char[][] map;
        char[] path;
        boolean[][] used;
        int rows;
        int cols;
        public boolean exist(char[][] board, String word) {
            if(board.length == 0 || board[0].length == 0) return false;
            if(word.length() == 0) return true;
            
            rows = board.length;
            cols = board[0].length;
            used = new boolean[rows][cols];
            map = board;
            path = word.toCharArray();
       
            for(int i = 0; i < rows; i++) {
                for(int j = 0; j < cols; j++) {
                    if(map[i][j] == path[0] && find(i, j, 0)) return true;
                }
            }
            
            return false;
        }
        
        private boolean find(int i, int j, int index) {
            if(index == path.length-1) return true;
            
            used[i][j] = true;
            
            if(i-1 >= 0 && !used[i-1][j] && map[i-1][j] == path[index+1]) {
                if(find(i-1, j, index+1)) return true;
            }
            if(i+1 < rows && !used[i+1][j] && map[i+1][j] == path[index+1]) {
                if(find(i+1, j, index+1)) return true;
            }
            if(j-1 >= 0 && !used[i][j-1] && map[i][j-1] == path[index+1]) {
                if(find(i, j-1, index+1)) return true;
            }
            if(j+1 < cols && !used[i][j+1] && map[i][j+1] == path[index+1]) {
                if(find(i, j+1, index+1)) return true;
            }
            
            used[i][j] = false;
            
            return false;
        }
    }
    

  • 0
    S

    By learning other's solution, I improve my solution

    public class Solution {
        char[][] map;
        char[] path;
        int rows;
        int cols;
    
        public boolean exist(char[][] board, String word) {
            if(board.length == 0 || board[0].length == 0) return false;
            if(word.length() == 0) return true;
            
            rows = board.length;
            cols = board[0].length;
            map = board;
            path = word.toCharArray();
       
            for(int i = 0; i < rows; i++) {
                for(int j = 0; j < cols; j++) {
                    if(map[i][j] == path[0] && find(i, j, 0)) return true;
                }
            }
            
            return false;
        }
        
        private boolean find(int i, int j, int index) {
            if(index == path.length-1) return true;
            
            map[i][j] ^= 256;
            
            if(i-1 >= 0 && map[i-1][j] == path[index+1]) {
                if(find(i-1, j, index+1)) return true;
            }
            if(i+1 < rows && map[i+1][j] == path[index+1]) {
                if(find(i+1, j, index+1)) return true;
            }
            if(j-1 >= 0 && map[i][j-1] == path[index+1]) {
                if(find(i, j-1, index+1)) return true;
            }
            if(j+1 < cols && map[i][j+1] == path[index+1]) {
                if(find(i, j+1, index+1)) return true;
            }
            
            map[i][j] ^= 256;
            
            return false;
            
        }
    }
    

Log in to reply
 

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