Word Search2

发布时间:2016-12-11 16:12:23 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Word Search2",主要涉及到Word Search2方面的内容,对于Word Search2感兴趣的同学可以参考一下。

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", -> returns true, word = "SEE", -> returns true, word = "ABCB", -> returns false. 这个题,怎么说呢,一个大的case过不了"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaab"], "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" 我还以为是dfs不行,因为之前在2d矩阵上写过深搜,用深搜来解决走迷宫的问题,效率确实很低,大部分时间路径都在一个相互连通的范围里打转。 想了想bfs,不可能啊,这个怎么都不能用bfs 最后发现是自己dfs的时候代码写错了,忘记把初始的访问标志置1,导致TLE class Solution { public: bool** flag; bool exist(vector<vector<char> > &board, string word) { if(board.size()==0) return false; if(board[0].size()==0) return false; if(word.length()>board[0].size()*board.size()) return false; flag = new bool*[board.size()]; for(int i=0;i<board.size();i++){ flag[i] = new bool[board[0].size()]; for(int j=0;j<board[0].size();j++) flag[i][j] = false; } for(int i=0;i<board.size();i++){ for(int j = 0;j<board[0].size();j++){ if(board[i][j]==word[0]){ flag[i][j] = true; bool shit = dfs(board,word,i,j,0); if(shit) return true; flag[i][j] = false; } } } return false; } int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; bool dfs(vector<vector<char> > &board, string word,int row,int col,int index){ if(index+1==word.length()) return true; if(board[row][col]!=word[index]) return false; for(int i = 0;i<4;i++){ int r = row+dir[i][0]; int c = col+dir[i][1]; if(r>-1 &&r<board.size() && c>-1 && c<board[0].size() && board[r][c]==word[index+1] && flag[r][c]==false){ flag[r][c] = true; bool shit = dfs(board,word,r,c,index+1); if(shit) return true; flag[r][c] = false; } } return false; } };有的时候,不是你想的算法解决不了问题,而是你的代码哪里写错了。要对自己分析问题的能力有信息,要对自己实现算法的能力继续提升,提升准确率。

上一篇:在iOS中创建静态库
下一篇:iOS KVO 观察者模式实现方式

相关文章

关键词: Word Search2

相关评论