思路:
This problem can be solved by using a typical DFS method.
時間 O(N^2) 空間 O(N)
我們知道一次搜索的復(fù)雜度是O(E+V)，E是邊的數(shù)量锋喜，V是頂點數(shù)量崔列，在這個問題中他們都是O(m*n)量級的（因為一個頂點有固定上下左右四條邊）。加上我們對每個頂點都要做一次搜索助泽，所以總的時間復(fù)雜度最壞是O(m^2*n^2)描睦，空間上就是要用一個數(shù)組來記錄訪問情況，所以是O(m*n)赘淮。
Time復(fù)雜度: 遍歷整個m * n 的board的時間復(fù)雜度為m * n,對于每個點都會往上下左右來遍歷尋找血公， k為word長度昵仅，大概要遍歷4^k次，所以總的時間復(fù)雜度大概在mn4^k.
Space： 由于word長度為k累魔，recursive space大概在O(k).
“以board上的每個cell為出發(fā)點摔笤，利用depth first search向上下左右四個方向搜索匹配word。搜索的時候要考慮board的邊界垦写，cell是否已經(jīng)在DFS的路徑上被用過吕世，以及cell上的值是否與word的當(dāng)前字符匹配。為了跟蹤DFS的路徑避免同一個cell被訪問多次梯投，使用一個visited矩陣來代表board上任意的cell(i, j)是否已經(jīng)被訪問過命辖。”
用圖, DFS遞歸.搜索的時候要注意邊界晚伙。把訪問過并且在word里面的點,存進一個visited數(shù)組中，防止重復(fù)使用字母俭茧。index為了防止word中的字母多次訪問咆疗。
最后visited要設(shè)為false，如果if的結(jié)果都是true的話母债，visited是什么都無妨午磁，但如果是false的話，說明這個數(shù)沒有用到毡们，所以要設(shè)為false迅皇。
第一步for循環(huán)外要return false ?因為如果訪問到最外層一定是因為for里面沒有返回true，所以一定是false的衙熔。
遞歸的時候要注意遞歸的出口登颓，結(jié)束當(dāng)前一層遞歸之后要返回上一層遞歸。
