leetcode做题笔记79单词搜索-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode做题笔记79单词搜索。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

思路一：回溯


bool sub_exist(char** board, int row, int col, char* word, int y, int x){
    
    if(*word == '\0')  
        return true;
    if(y < 0 || y >= row || x < 0 || x >= col || *word != board[y][x]
        return false;
    board[y][x] = '\0';  
    bool result = sub_exist(board, row, col, word + 1, y + 1, x) ||
                  sub_exist(board, row, col, word + 1, y - 1, x) ||
                  sub_exist(board, row, col, word + 1, y, x + 1) ||
                  sub_exist(board, row, col, word + 1, y, x - 1) ;
    board[y][x] = *word;        
    return result;
}


bool exist(char** board, int boardSize, int* boardColSize, char* word){

   

    for(int y = 0; y < boardSize; y ++){
        for(int x = 0; x < boardColSize[0]; x ++){
            if(board[y][x] == word[0] && sub_exist(board, boardSize, boardColSize[0], word, y, x))
                return true;
        }
    }
    return false;         
}