[leetcode] 79. Word Search

[leetcode] 79. Word Search

Description

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.

Example:

board =[ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']]Given word = "ABCCED", return true.Given word = "SEE", return true.Given word = "ABCB", return false.

分析

题目的意思是：判断字符矩阵中是否存在一条路径组成的单词等于题目给定的单词。

深度优先搜索题目，这是一个经典的递归搜索的题目，终止条件为遍历到word单词的末尾字符了。循环体注意不要超过这个矩阵的边界，因此需要isOut判断一下。

代码

class Solution {public: bool exist(vector>& board, string word) { int rows=board.size(); int cols=board[0].size(); for(int i=0;i>& board, string word,int start,int row,int col){ if(start>=word.size()){ return true; } if(isOut(row,col,board.size(),board[0].size())){ return false; } if(board[row][col]!=word[start]){ return false; } int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; char temp=board[row][col]; board[row][col]='.'; for(int i=0;i<4;i++){ if(DFS(board,word,start+1,row+dx[i],col+dy[i])){ return true; } } board[row][col]=temp; return false; } bool isOut(int row,int col,int rows,int cols){ return row<0||col<0||row>=rows||col>=cols; }};

参考文献

​​[编程题]word-search​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。