原题链接:http://oj.leetcode.com/problems/word-search/这道题很容易感觉出来是图的题目,其实本质上还是做深度优先搜索。基本思路就是从某一个元素出发,往上下左右深度搜索是否有相等于word的字符串。这里注意每次从一个元素出发时要重置访问标记(也就是说虽然单次搜索字符不能重复使用,但是每次从一个新的元素出发,字符还是重新可以用的)。深度优先搜索的算法就不再重复解释了,不了解的朋友可以看看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;
}
这道题其实还可以变一变,比如字符可以重复使用。准备的时候多联想还是比较好的,因为面试中常常会做完一道题会变一下问问,虽然经常不用重新写代码,但是想了解一下思路,有兴趣的朋友可以想想哈。
分享到:
相关推荐
void addWord(word) 将 word 添加到数据结构中,之后可以对它进行匹配bool search(word) 如果数据结构中存在字符串与 wor
硬字搜索IIhttps://leetcode.com/problems/word-search-ii/ EasyFind the Difference https://leetcode.com/problems/find-the-difference/ EasyWord 模式https://leetcode.com/problems/word-pattern/ 字符串中的 ...
扩展矩阵leetcode Leetcode Leetcode Answer-Java 数组 11.乘最多水容器 ...wordBreak 279.完全平方数 numSquares 排序 56.合并区间 merge 75.颜色分类 sortColors 179.最大数 largestNumber 324.摆
318| [Maximum Product of Word Lengths](https://leetcode.com/problems/maximum-product-of-word-lengths/) | [C++](./C++/maximum-product-of-word-lengths.cpp) [Python](./Python/maximum-product-of-word-...
hihocoder和leetcode leetcode 目录名 功能 Array 数组 Backtracking 回溯 Bit_Manipulation 位操作 Design 数据结构设计 ...单词搜索:word_search.cpp hihocoder String 文章重排:give_my_text_back.cpp
leetcode 苹果 LeetCode_No.208_-实现 Trie (前缀树) 题目介绍 Trie(发音类似 "try")或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完...
word源码java awesome-leetcode 用Java或者python实现的leetcode代码, java相关代码主要来源于 大佬,特此说明,感谢大佬的整理, 我只是为了方便继续写我的python代码,重新更改了许多文件。 Easy # Title Tag 1 ...
leetcode 耗时查词二 给定一个 2D 板和字典中的单词列表,找到板中的所有单词。 每个单词必须由顺序相邻单元格的字母构成,其中“相邻”单元格是水平或垂直相邻的单元格。 同一个字母单元格不能在一个单词中多次使用...
leetcode添加元素使和等于 October 2nd Reviews 79 word Search 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, ...
boolean search(String word) 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false 。 boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ...
leetcode 刷题笔记 记录一些刷题细节,很惭愧只做了一点微小的工作 4.13 162题. Find Peak Element.Binary search,需要比较nums[mid]和nums[mid+1]. 4.12 212题. Word Search II. 用trie tree存word list,然后dfs. ...
圆和椭圆重叠leetcode ——#158 尖端 关心特殊情况 从不同的方向思考 简单的 大批 1.Two Sum -> 使用哈希表避免遍历列表448.查找数组中消失的所有数字-> 1.建立缓冲区来计算数字| 2.使用数组作为带符号的缓冲区118....
search_word79.cpp。 链表基本操作要进行删除元素,那么在循环的过程中尽量使用前驱进行循环。提前校验head,head->next。new一个空头部。头插法pcur是空头后一位。 对于查找查找类的题目首先考虑二分查找,但是二分...
Search)+ 鸽笼原理(Pigeonhole Principle) “不允许修改数组” 与 “常数空间复杂度”这两个限制条件意味着:禁止排序,并且不能使用Map等数据结构 小于O(n2)的运行时间复杂度可以联想到使用二分将其中的一个n...
LeetCode一些 LeetCode 题目的进阶解法,追求极致效率。由于 LeetCode 已启用中文版域名 leetcode-... Word-Search-II题目: | 英文站源码:./problem-0212-Word-Search-II/标签:哈希表,双向链表难度:困难 / Hard
leetcode-按类别 看了一些leetcode刷题指南,总结一下两个重点,一是最好按照类别刷题,总结思路;二是由易到难,不要产生太大挫败感。 另外最好集中时间强度大一点来刷;还可以每个题只预留固定的思考时间,做不出...
leetcode 不会词搜索 给定一个 2D 板和一个单词,查找该单词是否存在于网格中。 单词可以由顺序相邻的单元格的字母构成,其中“相邻”单元格是水平或垂直相邻的单元格。 同一个字母单元格不能多次使用。 Example: ...
leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...
Search 解决方法:DFS LeetCode: 31. Next Permutation 解决方法:掌握排列组合的字典序规律,即可。这个规律找不到,我最后还是直接看答案的。 LeetCode: 581. Shortest Unsorted Continuous Subarray 解决方法:无...
leetcode 浇花力扣解决方案 简单的 #0001 - Two Sum #0007 - Reverse Integer #0009 - Palindrome Number #0035 - Search Insert Position #0058 - Length of Last Word #0066 - Plus One #0083 - Remove Duplicates...