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

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)