Leetcode/F家微软 -- 79. Word Search (backtracking)

79. Word Search(backtracking)
medium
https://leetcode.com/problems/word-search/

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Microsoft Bloomberg Facebook

思路： dfs each character in matrix to see if it can generate a path that match string.
           Make the visited node along the path invalid char by changing to '*', so we can avoid repeated search. Once return change back the letter to original.
(Or extra psace -- Use a visited[][] matrix to mark each visited node along the path)

Complexity: time O(mn*4^k) where k is the length of the string; mn for for loop and for the dfs method its 4^k.Since the dfs method goes only as deep as the word length we have T(k)=4(T(k-1))=4*4T(k-2)=....=.. which will be 4^k.
                     space O(4mn) if the function call stack is taken into account. In each cell, we recursively call its 4four neighbors and there are mn cells in total.

public class Solution {
    public boolean exist(char[][] board, String word) {
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[i].length; j++){
                if((word.charAt(0) == board[i][j]) && search(board, word, i, j, 0)){//fist half to save some search; index is for word
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean search(char[][]board, String word, int i, int j, int index){
        if(index == word.length())return true;
        if(i<0||i>=board.length||j<0||j>=board[0].length||word.charAt(index)!=board[i][j])return false;
        board[i][j] = '*';//or we can do borad[i][j]^=255, to make it not a valid letter
        boolean res = search(board,word,i-1,j,index+1)||search(board,word,i+1,j,index+1)||search(board,word,i,j-1,index+1)||search(board,word,i,j+1,index+1);
        board[i][j] = word.charAt(index);//recover by doing board[i][j]^=255
        return res;
    }
}