LeetCode题目:Word Search,回溯

By | 2012 年 11 月 8 日

回溯来解。
在back部分需要增加一段,因为对于word中第一个字符的位置是随意的;后面字符必须和前一个字符匹配位置相邻。



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.
For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = “ABCCED”, -> returns true,
word = “SEE”, -> returns true,
word = “ABCB”, -> returns false.



代码:284ms过大集合

struct Pos{
    int row;
    int col;
    Pos(int r, int c):row(r),col(c) {;}
};

class Solution {
public:
    bool exist(vector > &board, string word) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rows = board.size();
        if(0 == rows) return false;
        int cols = board[0].size();
        if(0 == cols) return false;
        
        if(0 == word.size()) return false;
        
        vector trace;
        trace.push_back(Pos(0,0));
        bool forward = true;
        while(trace.size() > 0) {
            int curIndex = trace.size() - 1;
            Pos &curPos = trace.back();
            if(forward) {
                //find a child
                if(curIndex >= word.size()) return true;
                char curChar = word[curIndex];
                //check out of board
                if( curPos.row < 0 
                    || curPos.row >= rows 
                    || curPos.col < 0 
                    || curPos.col >= cols ) {
                    forward = false;
                    continue;
                }
                //check repeat
                for(int i = 0; forward && i < trace.size() - 1; ++i) {
                    if(trace[i].row == curPos.row && trace[i].col == curPos.col) {
                        forward = false;
                        break;
                    }
                }
                if(!forward) continue;
                //go on
                if(board[curPos.row][curPos.col] == curChar) {
                    Pos nextPos(curPos.row,curPos.col);
                    --nextPos.row;//position above
                    trace.push_back(nextPos);
                } else {
                    forward = false;
                }
            } else {
                if(trace.size() == 1) {
                    //first char in word ,find next available one
                    if(trace[0].row == rows - 1 && trace[0].col == cols - 1) {
                        //no available
                        trace.pop_back();
                    } else {
                        ++ trace[0].col;
                        if(trace[0].col == cols) {
                            trace[0].col = 0;
                            trace[0].row = trace[0].row + 1;
                        }
                        forward = true;
                    }
                } else {
                    Pos &lastpos = trace[trace.size() - 2];
                    //order as : above, right, down, left
                    if(curPos.col == lastpos.col) {
                        if(curPos.row < lastpos.row) {
                            //above to right
                            curPos.col = lastpos.col + 1;
                        } else {
                            //down to left
                            curPos.col = lastpos.col - 1;
                        }
                        curPos.row = lastpos.row;
                        forward = true;
                    } else {
                        if (curPos.col > lastpos.col) {
                            //right to down
                            curPos.row = lastpos.row + 1;
                            curPos.col = lastpos.col;
                            forward = true;
                        } else {
                            //no available
                            trace.pop_back();
                        }
                    }
                }
            }// end back if
        }//end while
        return false;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注