# Word Search ### Source - leetcode: [Word Search | LeetCode OJ](https://leetcode.com/problems/word-search/) - lintcode: [(123) Word Search](http://www.lintcode.com/en/problem/word-search/) ### Problem 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 Given board = ~~~ [ "ABCE", "SFCS", "ADEE" ] ~~~ - word = `"ABCCED"`, -> returns `true`, - word = `"SEE"`, -> returns `true`, - word = `"ABCB"`, -> returns `false`. ### 題解 典型的 [DFS](# "Depth-First Search, 深度優先搜索") 實現，這里有上下左右四個方向，往四個方向遞歸之前需要記錄坐標處是否被訪問過，并且在不滿足條件時要重置該標記變量。該題的一大難點是如何處理起始點和字符串的第一個字符不等的情況，我最開始嘗試在一個 [DFS](# "Depth-First Search, 深度優先搜索") 中解決，發現很難 bug-free, 而且程序邏輯支離破碎。后來看了下其他題解發現簡單粗暴的方法就是雙重循環嵌套 [DFS](# "Depth-First Search, 深度優先搜索")... ### Java ~~~ public class Solution { /** * @param board: A list of lists of character * @param word: A string * @return: A boolean */ public boolean exist(char[][] board, String word) { if (board == null || board.length == 0 || board[0].length == 0) return false; if (word == null || word.length() == 0) return false; boolean[][] visited = new boolean[board.length][board[0].length]; for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if (dfs(board, word, visited, i, j, 0)) { return true; } } } return false; } public boolean dfs(char[][] board, String word, boolean[][] visited, int row, int col, int wi) { // out of index if (row < 0 || row > board.length - 1 || col < 0 || col > board[0].length - 1) { return false; } if (!visited[row][col] && board[row][col] == word.charAt(wi)) { // return instantly if (wi == word.length() - 1) return true; // traverse unvisited row and col visited[row][col] = true; boolean down = dfs(board, word, visited, row + 1, col, wi + 1); boolean right = dfs(board, word, visited, row, col + 1, wi + 1); boolean up = dfs(board, word, visited, row - 1, col, wi + 1); boolean left = dfs(board, word, visited, row, col - 1, wi + 1); // reset with false if none of above is true visited[row][col] = up || down || left || right; return up || down || left || right; } return false; } } ~~~ ### 源碼分析 注意處理好邊界退出條件及`visited`在上下左右四個方向均為`false`時需要重置。判斷字符串字符和`board`中字符是否相等前需要去掉已訪問坐標。如果不引入`visited`二維矩陣，也可以使用特殊字符替換的方法，這樣的話空間復雜度就大大降低了，細節見下面參考鏈接。 ### 復雜度分析 [DFS](# "Depth-First Search, 深度優先搜索") 最壞情況下遍歷所有坐標點，二重 for 循環最壞情況下也全部執行完，故時間復雜度最差情況下為 O(m2n2)O(m^2n^2)O(m2n2), 使用了`visited`矩陣，空間復雜度為 O(mn)O(mn)O(mn), 當然這個可以優化到 O(1)O(1)O(1).(原地更改原 board 數組字符內容)。 ### Reference - [LeetCode – Word Search (Java)](http://www.programcreek.com/2014/06/leetcode-word-search-java/)