Leetcode Word Search

复盘:

缺少边界条件判断

判断area和visited的位置错误地提前了

重复make了一维map

没画图
没用测试用例走伪代码和图
没用测试用例走伪代码和图到超出边界的情况

我认为只要走两个测试用例 , 都能发现大部分错误 , 走点心吧

func exist(board [][]byte, word string) bool {
    for row, rowdata := range board {
        s := Solution{visited: make(map[int]map[int]bool)}
        res := false
        for col, _ := range rowdata {
            res = s.wordSearch(word, 0, len(word)-1, board, col, row)
            if res == true {
                return true
            }
        }
    }
    return false
}

type Solution struct {
    visited map[int]map[int]bool
}

func (t *Solution) wordSearch(word string, wordhead int, wordend int, board [][]byte, startcol int, startrow int) bool {
    if wordhead == len(word)-1 {
        return word[wordhead] == board[startrow][startcol]
    }

    if board[startrow][startcol] == word[wordhead] {
        coord := [][]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}} //up right down  left
        if _,ok:=t.visited[startrow];!ok {
            t.visited[startrow] = make(map[int]bool)
        }
        t.visited[startrow][startcol] = true
        for _, v := range coord {
            newrow := startrow + v[0]
            newcol := startcol + v[1]
            if inArea(newcol, newrow, board) && !t._visited(newcol, newrow) {

                res := t.wordSearch(word, wordhead+1, wordend, board, newcol, newrow)
                if res == true {
                    return true
                }

            }
        }
        delete(t.visited[startrow], startcol)
    }
    return false

}

func inArea(col int, row int, board [][]byte) bool {
    return row >= 0 && row <= len(board)-1 && col >= 0 && col <= len(board[0])-1
}

func (t *Solution) _visited(col int, row int) bool {
    if _, ok := t.visited[row][col]; ok {
        return true

    } else {
        return false
    }
}

definition

search $word range [$wordhead,$wordend] in $board        , start from $startcol , $startrow  , if found , return true , else false  

wordSearch ( word , wordhead , wordend , board , startcol , startrow ) {

    if in area and not visted {
        if board[startrow][startcol] equal word[wordhead] {
            find around with order up right down left 
                mark board[startrow][startcol] as visited
                res =  -> wordSearch(word,wordHead+1,wordend,board,newcol,newrow)
                if res found , return true
                else unmark board[startrow][startcol] as unvisted 
                continue try another direction
                if all direction not found , return false   
        } else {
            return false
        }
    } else {
        return false
    }
}

class Solution {

private:
    int d[4][2] = {{-1, 0}, {0,1}, {1, 0}, {0, -1}};
    int m, n;
    vector<vector<bool>> visited;

    bool inArea(int x, int y){
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    // 从board[startx][starty]开始, 寻找word[index...word.size())
    bool searchWord(const vector<vector<char>> &board, const string& word, int index,
                    int startx, int starty ){

        //assert(inArea(startx,starty));
        if(index == word.size() - 1)
            return board[startx][starty] == word[index];

        if(board[startx][starty] == word[index]){
            visited[startx][starty] = true;
            // 从startx, starty出发,向四个方向寻
            for(int i = 0 ; i < 4 ; i ++){
                int newx = startx + d[i][0];
                int newy = starty + d[i][1];
                if(inArea(newx, newy) && !visited[newx][newy] &&
                   searchWord(board, word, index + 1, newx, newy))
                    return true;
            }
            visited[startx][starty] = false;
        }
        return false;
    }

public:
    bool exist(vector<vector<char>>& board, string word) {

        m = board.size();
        assert(m > 0);
        n = board[0].size();
        assert(n > 0);

        visited.clear();
        for(int i = 0 ; i < m ; i ++)
            visited.push_back(vector<bool>(n, false));

        for(int i = 0 ; i < board.size() ; i ++)
            for(int j = 0 ; j < board[i].size() ; j ++)
                if(searchWord(board, word, 0, i, j))
                    return true;

        return false;
    }
};

本作品采用《CC 协议》，转载必须注明作者和本文链接