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.

Example:

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

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

时间复杂度 不确定 o(m*n*4^k), 4:上下左右 dfs， k word的长度，m，n矩阵长宽，

space o(word length)

class Solution {
    public boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0 || board[0].length == 0)
            return false;
        
        
        for(int i = 0; i < board.length;i++){
            for(int j = 0; j < board[0].length;j++){
                if(exist(board,i,j,word,0 )){
                    return true;
                }
            }
        }
        
        return false;
    }
    
    public boolean exist(char[][] board, int i, int j, String word, int start){
        if(start >= word.length()) return true;
        
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length){
            return false;
        }
        
        if(board[i][j] == word.charAt(start++)){
            char c =board[i][j];
            board[i][j] = '#';
            boolean res = exist(board,i+1,j,word,start) || 
                            exist(board,i-1,j,word, start)||
                            exist(board,i,j+1,word, start)||
                            exist(board,i,j-1,word,start);
            
            board[i][j] = c;
            
            return res;
        }
        
        return false;
    }
}

word search，脑补题目为从一个字符矩阵中搜索某个字符串是否存在，可以向四个方向延伸。那么dfs和bfs的时间复杂度是指数级别的，大概是4的字符串长度次方，因为每次都可能走四个方向（实际上比这个低，因为不一定四个方向都可以走，也可能走过的地方不能走，但是给出最坏情况就可以了） 2.某些需要使用visit数组的搜索问题，因为每个位置至多访问一边，所以时间复杂度是多项式级别的，通常是地图大小。

如果你的问题是宏观的如何分析复杂度，当没法直接统计循环次数的时候，就需要借助某些变量（比如只递增的变量）、数组（比如每个位置只遍历常数次的标记数组）等来统计总共搜索的次数。而对于指数级，并不需要精确分析，大概给出底数和指数就可以了。