[Java] LTE in longest test case


  • 0
    L

    I am using DFS and i return true early when meet the requirement, not sure why still get TLE here...

        public class Solution {
        public boolean exist(char[][] board, String word) {
            int m = board.length;
            int n = board[0].length;
            int len = word.length();
            if(m * n < len || word.length() == 0) {
                return false;
            }
            
            boolean found = false;
            for(int j = 0; j < m; j++){
                for(int k = 0; k < n; k++){
                    boolean[][] visited = new boolean[m][n];
                    if(board[j][k] == word.charAt(0)){
                        found = findNextChar(board, j, k, 1, word, visited);
                        if(found){
                            return true;
                        }
                    }
                }
            }
            return false;       
        }
        
         boolean findNextChar(char[][] board, int j, int k, int charIndex, String word, boolean[][] visited) {
            boolean found = false;
            int m = board.length;
            int n = board[0].length;
            visited[j][k] = true;
            if (charIndex >= word.length()) {
                return true;
            }
    
            if (j - 1 >= 0 && !visited[j - 1][k] && board[j - 1][k] == word.charAt(charIndex)) {
                found = findNextChar(board, j - 1, k, charIndex + 1, word, visited);
                if (found) {
                    return true;
                }
            }
            if (j + 1 <= m - 1 && !visited[j + 1][k] && board[j + 1][k] == word.charAt(charIndex)) {
                found = findNextChar(board, j + 1, k, charIndex + 1, word, visited);
                if (found) {
                    return true;
                }
            }
            if (k - 1 >= 0 && !visited[j][k - 1] && board[j][k - 1] == word.charAt(charIndex)) {
                found = findNextChar(board, j, k - 1, charIndex + 1, word, visited);
                if (found) {
                    return true;
                }
            }
            if (k + 1 <= n - 1 && !visited[j][k + 1] && board[j][k + 1] == word.charAt(charIndex)) {
                found = findNextChar(board, j, k + 1, charIndex + 1, word, visited);
                if (found) {
                    return true;
                }
            }
            return false;
        }
    }
    

    Can anyone help me?


  • 0
    B

    Dear lu.tong,

    I think you allocate too many memory. I suggest that the following allocation move outside of the for loop

    boolean[][] visited = new boolean[m][n];
    

    Namely, changing the original codes as follows

          boolean[][] visited = new boolean[m][n]; 
          for(int j = 0; j < m; j++){
              for(int k = 0; k < n; k++){
                    if(board[j][k] == word.charAt(0)){
                        found = findNextChar(board, j, k, 1, word, visited);
                        if(found){
                            return true;
                        }
                    }
                }
            }
    

    Also you need to restore the state of visited array at the end of findNextChar() as follows.

     visited[j][k] = false;
     return false;
    

    Good luck. P.s. I have tested your codes with the above two changes. It got an AC.


  • 0
    L

    Thanks, that really helps!


Log in to reply
 

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