[LeetCode][Java] Word Search
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[LeetCode][Java] Word Search,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2180字,纯文字阅读大概需要4分钟。
内容图文
题目:
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
.
题意:
给定一个二维的模板,在格子中寻找一个单词,看其是否存在。
这个单词是由格子中的相邻的紧挨的水平或者竖直方向的元素构成的。同一个字母元素只能被使用一次。
For example,
Given board =
[
["ABCE"],
["SFCS"],
["ADEE"]
]
word
=
"ABCCED"
,
-> returns
true
,
word =
"SEE"
,
-> returns
true
,
word =
"ABCB"
,
-> returns
false
.
算法分析:
参考博客http://blog.csdn.net/linhuanmars/article/details/24336987
这道题很容易感觉出来是图的题目,其实本质上还是做
深度优先搜索
。基本思路就是从某一个元素出发,往上下左右深度搜索是否有相等于word的字符串。这里注意每次从一个元素出发时要重置访问标记(也就是说虽然单次搜索字符不能重复使用,但是每次从一个新的元素出发,字符还是重新可以用的)。深度优先搜索的算法就不再重复解释了,不了解的朋友可以看看
wiki - 深度优先搜索
。我们知道一次搜索的复杂度是O(E+V),E是边的数量,V是顶点数量,在这个问题中他们都是O(m*n)量级的(因为一个顶点有固定上下左右四条边)。加上我们对每个顶点都要做一次搜索,所以总的时间复杂度最坏是O(m^2*n^2),空间上就是要用一个数组来记录访问情况,所以是O(m*n)。
AC代码:
<span style="font-family:Microsoft YaHei;font-size:12px;">public class Solution { public boolean exist(char[][] board, String word) { if(word==null || word.length()==0) return true; if(board==null || board.length==0 || board[0].length==0) return false; boolean[][] used = new boolean[board.length][board[0].length]; for(int i=0;i<board.length;i++) { for(int j=0;j<board[0].length;j++) { if(search(board,word,0,i,j,used)) return true; } } return false; } private boolean search(char[][] board, String word, int index, int i, int j, boolean[][] used) { if(index == word.length()) return true; if(i<0 || j<0 || i>=board.length || j>=board[0].length || used[i][j] || board[i][j]!=word.charAt(index)) return false; used[i][j] = true; boolean res = search(board,word,index+1,i-1,j,used) || search(board,word,index+1,i+1,j,used) || search(board,word,index+1,i,j-1,used) || search(board,word,index+1,i,j+1,used); used[i][j] = false; return res; } }</span>
版权声明:本文为博主原创文章,转载注明出处
原文:http://blog.csdn.net/evan123mg/article/details/46941589
内容总结
以上是互联网集市为您收集整理的[LeetCode][Java] Word Search全部内容,希望文章能够帮你解决[LeetCode][Java] Word Search所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。