Exceed time limit for the case : aaaa,aaaa,........, baaaaaaaaa


  • 1
    S

    For this case, my method will only run M*N times. Why it will exceed time limit?

    public class Solution {
            private int[] xShift = new int[] {-1, 0, 0, 1};
            private int[] yShift = new int[] {0, -1, 1, 0};
            
            public boolean exist (char[][] board, String word) {
        		if (board == null || board.length == 0) return false;
        		if (word == null || word.length() == 0) return true;
        		if (board.length * board[0].length < word.length()) return false;
        
        		for (int i = 0; i < board.length; i++) {
        			for (int j = 0; j < board[0].length; j++) {
        				if (dfs(board, word, i, j, 0)) return true;
        			}
        		}
        
        		return false;
        	}
        
        	private boolean dfs(char[][] board, String word, int iStart, int jStart, int index) {
        		if (index == word.length()) {
        			return true;
        		}
        
        		if (board[iStart][jStart] != word.charAt(index)) return false;
        		char curr = board[iStart][jStart];
        		board[iStart][jStart] = '#';
                
                for (int k = 0; k < 4; k++) {
                    int i = iStart - xShift[k];
                    int j = jStart - yShift[k];
                    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length 
                        || board[i][j] == '#') continue;
        			if (dfs(board, word, i, j, index + 1)) {
        				//very important
        				board[iStart][jStart] = curr;
        				return true;
        			}
                }
        
        		board[iStart][jStart] = curr;
        
        		return false;
        
        	}
        }

  • 0
    I

    reorder your code:

    if (board[iStart][jStart] != word.charAt(index)) return false;
    else{
        index++;
        if (index == word.length()) 
        return true;
    }
    

    Btw:

    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == '#') continue;
    

    should change to

    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length ) continue;
    

    and

    if (dfs(board, word, i, j, index + 1))    
    board[iStart][jStart] = curr;
    

    change to

    if (dfs(board, word, i, j, index))

Log in to reply
 

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