Leetcode 212. 单词搜索 II(DAY 114) ---- 回溯算法学习期
2021/5/16 20:27:04
本文主要是介绍Leetcode 212. 单词搜索 II(DAY 114) ---- 回溯算法学习期,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 原题题目
- 代码实现(首刷TLE 39\40)
- 代码实现(首刷自解优化 双超80)
原题题目
代码实现(首刷TLE 39\40)
class Solution { public: bool backtracking(const vector<vector<char>>& board,vector<vector<bool>>& visit,vector<string>& ret,const string& word,int pos,int x,int y) { if(x<0 || x>=board.size() || y<0 || y>= board[0].size() || word[pos] != board[x][y] || visit[x][y]) return false; if(pos == word.size()-1) { ret.emplace_back(word); return true; } int flag = 0; visit[x][y] = true; if(backtracking(board,visit,ret,word,pos+1,x+1,y) || backtracking(board,visit,ret,word,pos+1,x-1,y) || backtracking(board,visit,ret,word,pos+1,x,y+1) || backtracking(board,visit,ret,word,pos+1,x,y-1)) flag = 1; visit[x][y] = false; if(flag) return true; else return false; } vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { vector<vector<bool>> visit(board.size(),vector<bool>(board[0].size(),false)); vector<string> ret; int count = 0; vector<bool> wordjudge(words.size(),false); for(int i=0;i<board.size();++i) { for(int j=0;j<board[0].size();++j) { for(int k=0;k<wordjudge.size();++k) { int flag = 0; if(wordjudge[k] || board[i][j] != words[k][0]) continue; if(backtracking(board,visit,ret,words[k],0,i,j)) { ++count; wordjudge[k] = true; } } if(count == wordjudge.size()) return ret; } } return ret; } };
代码实现(首刷自解优化 双超80)
class Solution { public: bool backtracking(const vector<vector<char>>& board,vector<vector<bool>>& visit,vector<string>& ret,const string& word,int pos,int x,int y) { if(x<0 || x>=board.size() || y<0 || y>= board[0].size() || word[pos] != board[x][y] || visit[x][y]) return false; if(pos == word.size()-1) { ret.emplace_back(word); return true; } int flag = 0; visit[x][y] = true; if(backtracking(board,visit,ret,word,pos+1,x+1,y) || backtracking(board,visit,ret,word,pos+1,x-1,y) || backtracking(board,visit,ret,word,pos+1,x,y+1) || backtracking(board,visit,ret,word,pos+1,x,y-1)) flag = 1; visit[x][y] = false; if(flag) return true; else return false; } vector<string> findWords(vector<vector<char>>& board, vector<string>& words) { vector<vector<bool>> visit(board.size(),vector<bool>(board[0].size(),false)); vector<string> ret,temp; unordered_set<char> set; int count = 0; for(const auto& row:board) for(const auto& chr:row) set.emplace(chr); for(const auto& word:words) { int flag = 0; for(const auto& chr:word) { if(set.find(chr) != set.end()) continue; flag = 1; break; } if(!flag) temp.emplace_back(word); } words = temp; vector<bool> wordjudge(words.size(),false); for(int i=0;i<board.size();++i) { for(int j=0;j<board[0].size();++j) { for(int k=0;k<wordjudge.size();++k) { int flag = 0; if(wordjudge[k] || board[i][j] != words[k][0]) continue; if(backtracking(board,visit,ret,words[k],0,i,j)) { ++count; wordjudge[k] = true; } } if(count == wordjudge.size()) return ret; } } return ret; } };
这篇关于Leetcode 212. 单词搜索 II(DAY 114) ---- 回溯算法学习期的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享