Ac solution code


  • 0

    The basic idea is using DFS to check each node in the matrix, extending to its 4-direction neighbors.

    Time complexity in Worst Case = O(nm) * O(4 ^ ((nm)/4) ) - Any advice would be appreciated!**

    O(n*m): 2 loops to check each node;

    O(4 ^ ((nm)/4) ): For each node, there're 4 directions. Ignoring visited nodes, there're (nm)/4) check points.

    Time complexity in Average =: O(nm) + O(4 ^ ((nm)/4) )**

    Because in the average time, DFS will stop once the current string is not the prefix of the input string. As we only need to find one correct path, the time complexity: O(nm) + O(4 ^ ((nm)/4) ).

    JAVA Code:

    private final Point directions[] = {new Point(-1, 0), new Point(1, 0),  new Point(0, -1), new Point(0, 1)};	
    public boolean exist(char[][] board, String word) {
    	if (board == null || board.length == 0) return false;	
    	int n = board.length, m = board[0].length;
    	boolean visited[][] = new boolean[n][m];
    	char[] chs = word.toCharArray();
    	
    	for (int i = 0; i < n; i++) {// O(n*m) 
    		for (int j = 0; j < m; j++) {
    			if (DFS(board, i, j, visited, 0, word.toCharArray()))
    				return true;
    		}
    	}
    	return false;
    }	
    // cur - index of the tracing string
    // O(4 ^ ((n*m)/4) )
    boolean DFS(char[][] board, int i, int j, boolean[][] visited, int cur, char[] word) {				
        if (cur == word.length) return true;
    	if (i < 0 || i > visited.length - 1 || j < 0 || j > visited[0].length - 1) return false;//<-check current node
        if (visited[i][j]) return false;
        if (word[cur] != board[i][j]) return false;
        
    	visited[i][j] = true;
    	for (Point direction : directions) {// 4 neighbors: up, down, left, right
    		int row = i + direction.x;
    		int col = j + direction.y;
    			if (DFS(board, row, col, visited, cur + 1, word)) 
    				return true;							
    	}
    	visited[i][j] = false;
    	return false; 
    }

Log in to reply
 

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