首页 > 代码库 > [leetcode]Word Search
[leetcode]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"
, -> returnstrue
,word =
"SEE"
, -> returns true
,word =
"ABCB"
, -> returns false
.思路:
回溯法,找到一个可行解即可。
此题根据每个字符位置,找和它邻近的位置(上下左右)是否是word的下一个字符。每次考虑这四种情况。
同时本题中要求每个相同位置的字符只能用一次。所以要用记事本record记录已经用了哪些位置的字符。
代码:
class Solution { //C++ public: bool exist(vector<vector<char> > &board, string word) { if(board.size() == 0) return false; if(word == "") return true; vector<vector<int> > record; for(int i = 0; i < board.size(); i++){ vector<int > tmp ; for(int j = 0; j < board[0].size(); j++) tmp.push_back(0); record.push_back(tmp); } int size = word.size(); for(int i = 0; i < board.size(); i++){ for(int j = 0; j < board[0].size(); j++){ if(board[i][j] == word[0]){ record[i][j] = 1; if(isExist(board, word.substr(1,size-1),i,j,record)) return true; record[i][j] = 0; } } } return false; } bool isExist(vector<vector<char> > &board, string word, int row, int col,vector<vector<int> > &record){ if(word.size() == 0){ return true; } // up down left right bool up = false , down = false, left = false, right =false; int size = word.size(); int frow = 0, fcol = 0, erow = board.size()-1, ecol = board[0].size()-1; // up if(row != frow && record[row-1][col] == 0 && word[0] == board[row-1][col]){ if(size == 1) return true; else { record[row-1][col] = 1; up = isExist(board,word.substr(1,size-1),row-1,col,record); record[row-1][col] = 0; } if(up == true) return true; } // down if(row != erow && record[row+1][col] == 0 &&word[0] == board[row+1][col]){ if(size == 1) return true; else { record[row+1][col] = 1; down = isExist(board,word.substr(1,size-1),row+1,col,record); record[row+1][col] = 0; } if(down == true) return true; } // left if(col != fcol && record[row][col-1] == 0 &&word[0] == board[row][col-1]){ if(size == 1) return true; else { record[row][col-1] = 1; left = isExist(board,word.substr(1,size-1),row,col-1,record); record[row][col-1] = 0; } if(left == true) return true; } // right if(col != ecol && record[row][col+1] == 0 &&word[0] == board[row][col+1]){ if(size == 1) return true; else { record[row][col+1] = 1; right = isExist(board,word.substr(1,size-1),row,col+1,record); record[row][col+1] = 0; } if(right == true) return true; } return false; } };
[leetcode]Word Search
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。