JS技术

Word Search -- LeetCode - Code Ganker - 博客频道 - CSDN.NET Code

字号+ 作者:H5之家 来源:H5之家 2015-12-15 08:56 我要评论( )

USB Mass Storage类规范概述 USB Mass storage Device协议即海量存储设备协议适用于硬盘,U盘等大容量存储设备。协议使用的接口端点有BulkIn、BulkOut和Interrup


wiki - 深度优先搜索。我们知道一次搜索的复杂度是O(E+V),E是边的数量,V是顶点数量,在这个问题中他们都是O(m*n)量级的(因为一个顶点有固定上下左右四条边)。加上我们对每个顶点都要做一次搜索,所以总的时间复杂度最坏是O(m^2*n^2),空间上就是要用一个数组来记录访问情况,所以是O(m*n)。代码如下: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; }这道题其实还可以变一变,比如字符可以重复使用。准备的时候多联想还是比较好的,因为面试中常常会做完一道题会变一下问问,虽然经常不用重新写代码,但是想了解一下思路,有兴趣的朋友可以想想哈。

  • 上一篇Subsets -- LeetCode
  • 下一篇Remove Duplicates from Sorted Array II -- LeetCode
  • 顶 61 踩 3

    我的同类文章

    猜你在找

    查看评论

    * 以上用户言论只代表其个人观点,不代表CSDN网站的观点或立场

    个人资料


    linhuanmars

  • 访问:1293842次
  • 积分:24056
  • 等级:

    积分:24056

  • 排名:第140名
  • 文章搜索

    博客专栏

    LeetCode总结

    文章:154篇

    阅读:1179959

    文章分类

  • LeetCode(155)
  • LeetCode总结(14)
  • 文章存档

    阅读排行

  • Substring with Concatenation of All Words -- LeetCode(15968)
  • N-Queens -- LeetCode(15816)
  • Divide Two Integers -- LeetCode(14798)
  • Merge k Sorted Lists -- LeetCode(14761)
  • Wildcard Matching -- LeetCode(13298)
  • Best Time to Buy and Sell Stock III -- LeetCode(13172)
  • Sudoku Solver -- LeetCode(12829)
  • Maximum Product Subarray -- LeetCode(12699)
  • 4Sum -- LeetCode(12540)
  • Minimum Window Substring -- LeetCode(12283)
  • 评论排行

  • Best Time to Buy and Sell Stock III -- LeetCode(54)
  • Substring with Concatenation of All Words -- LeetCode(34)
  • Word Break II -- LeetCode(30)
  • Flatten Binary Tree to Linked List -- LeetCode(30)
  • Surrounded Regions -- LeetCode(24)
  • Divide Two Integers -- LeetCode(22)
  • Pow(x, n) -- LeetCode(22)
  • Sort List -- LeetCode(21)
  • Add Binary -- LeetCode(20)
  • Wildcard Matching -- LeetCode(20)
  • 推荐文章

  • *Hadoop节点"慢磁盘"监控
  • *假如你想成为全栈工程师…
  • *没有躲过的坑--正则表达式截取字符串
  • *CardView完全解析与RecyclerView结合使用(三十二)
  • *And roid 高仿微信发朋友圈浏览图片效果
  • *通过Ajax的方式执行GP服务
  • 最新评论

  • windforce89: @baidu_32569483:感觉那个'0'并不太要紧。根据题意输入的board数组内的元素肯定都...

  • helloworldsss: thx! I AM from usa.

  • pinkfloyda: 刚做了这道题,看了楼主的答案,有点问题max_local = Math.max(Math.max(A...

  • linhuanmars: @majestyhao:因为这里如果diff比0小,那么不如不要这次交易,或者认为是当天买当天卖~

  • linhuanmars: @u011484134:这个没有资料,我上面用数学证明过了哈~ 就是环之前的领先步数会在环内走时被追...

  • linhuanmars: @duolasuo:其实这里用一个数据结构存也可以,只是为了面试时不用多搞一个数据结构,所以编码了一...

  • linhuanmars: @feliciafay:不是做图像处理的哈,只是做过相关的project~

  • linhuanmars: @paul920531:恩,应该是的哈~

  • linhuanmars: @u011861751:因为java都是按值传递,所以如果要使一个变量在全局域有效,只能通过一个数组...

  • linhuanmars: @test110112:时间复杂度是不同的哇~ 数量小的时候可能看不出来,试试大一点的数字就看出区别...

     

    1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

    相关文章
    • LeetCode 263:Ugly Number - geekmanong的专栏 - 博客频道 - CSDN.NET g

      LeetCode 263:Ugly Number - geekmanong的专栏 - 博客频道 - CSDN.NE

      2015-12-13 12:20

    • leetcode笔记:Spiral Matrix - liyuefeilong的专栏 - 博客频道 - CSDN.NET

      leetcode笔记:Spiral Matrix - liyuefeilong的专栏 - 博客频道 - CS

      2015-12-13 12:03

    • 利用Yahoo! Search API开发自已的搜索引擎-javascript版_javascript教程教程

      利用Yahoo! Search API开发自已的搜索引擎-javascript版_javascript

      2015-10-08 11:15

    • JavaScript Web页面内容导出到Word、Excel_javascript教程教程

      JavaScript Web页面内容导出到Word、Excel_javascript教程教程

      2015-10-08 10:37

    网友点评