柚子快报激活码778899分享：leetcode第一刷
这道题之前一直没敢做，没想到前天用递归一遍过了。。
当时为什么想着用递归，而不是dp呢。由于我想到达某个位置的情况有非常多，即使从当前位置開始的搜索是已知的，但之前的状态是如何的也无从得知啊，实话实说，我是不会用dp解这个。。
递归的思路就好说多了，从当前点開始。有上下左右四个位置能够探測，假设探測成功的话，要把当前的位置用其它符号标记出来，以免反复訪问。实际上就是DFS嘛。仅仅只是入口多一些。
须要注意的一点是，每一个点都能够作为起点。所以这个要穷举一下。否则会漏掉情况的。当然有一种情况走通就能够返回了。剪枝之。
代码又臭又长，只是work：
class Solution {
public:
int row, column;
bool doexist(vector
if(len == word.length()) return true;
bool res;
if(i>0&&board[i-1][j] == word[len]){
board[i-1][j] = '.';
res = doexist(board, word, len+1, i-1, j);
if(res) return true;
else board[i-1][j] = word[len];
}
if(i board[i+1][j] = '.'; res = doexist(board, word, len+1, i+1, j); if(res) return true; else board[i+1][j] = word[len]; } if(j>0&&board[i][j-1] == word[len]){ board[i][j-1] = '.'; res = doexist(board, word, len+1, i, j-1); if(res) return true; else board[i][j-1] = word[len]; } if(j board[i][j+1] = '.'; res = doexist(board, word, len+1, i, j+1); if(res) return true; else board[i][j+1] = word[len]; } return false; } bool exist(vector row = board.size(); if(row == 0) return false; column = board[0].size(); char c; for(int i=0;i for(int j=0;j if(board[i][j] == word[0]){ board[i][j] = '.'; if(doexist(board, word, 1, i, j)) return true; board[i][j] = word[0]; } } } return false; } }; 柚子快报激活码778899分享：leetcode第一刷 参考阅读
发表评论