首页 > 其他 > 详细

leetcode第一刷_Word Search

时间:2014-05-11 14:19:22      阅读:336      评论:0      收藏:0      [点我收藏+]

这道题之前一直没敢做,没想到前天用递归一遍过了。。

当时为什么想着用递归,而不是dp呢,因为我想到达某个位置的情况有很多,即使从当前位置开始的搜索是已知的,但之前的状态是怎样的也无从得知啊,实话实说,我是不会用dp解这个。。

递归的思路就好说多了,从当前点开始,有上下左右四个位置可以探测,如果探测成功的话,要把当前的位置用其他符号标记出来,以免重复访问。实际上就是DFS嘛,只不过入口多一些。

需要注意的一点是,每个点都可以作为起点,所以这个要穷举一下,否则会漏掉情况的。当然有一种情况走通就可以返回了,剪枝之。

代码又臭又长,不过work:

class Solution {
public:
    int row, column;
    bool doexist(vector<vector<char> > &board, string &word, int len, int i, int j){
        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<row-1&&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(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<column-1&&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];
        }
        return false;
    }
    bool exist(vector<vector<char> > &board, string word) {
        row = board.size();
        if(row == 0)    return false;
        column = board[0].size();
        char c;
        for(int i=0;i<row;i++){
            for(int j=0;j<column;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;
    }
};


leetcode第一刷_Word Search,布布扣,bubuko.com

leetcode第一刷_Word Search

原文:http://blog.csdn.net/u012792219/article/details/25472091

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!