`
huntfor
  • 浏览: 194199 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetcode]Word Search

 
阅读更多

第二遍的做法居然跟第一遍完全一样:

新博文地址:[leetcode]Word Search

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, 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.

好多天没刷题了,手都生了。。。

迷宫问题是回溯算法的典型应用,这道题就是典型的回溯算法,比较烦人的一点是不许走回头路,一种方法是将走过的节点做出标记(不需要改变原矩阵);另一种做法就是走过的节点就删掉(需要改变原矩阵),这样就不会走回头路了。我采取的是后一种。

顺序扫描board矩阵,遇到跟word第一个字母相同的节点就开始上下左右搜索,以SEE为例:

 

遇到第一个S,board[1][0],将该S删掉,以防走回头路,然后继续dfs,发现无论怎么走都不满足条件,ok,说明此路不通,将方才删掉的S重新加上去。

 

遇到第二个S,board[1][3],dfs之,发现可以向上走,找到E,board[0][3],然后此路不通了,将删掉的E添加上,并重新回溯到S,发现下面还有路可能走的通,找到E之后发现还可以向左走,然后就木有然后了。

public boolean exist(char[][] board, String word) {
		int height = board.length;
		int length = board[0].length;
		if (height * length < word.length()) {
			return false;
		}

		for (int row = 0; row < height; row++) {
			for (int column = 0; column < length; column++) {
				if (board[row][column] == word.charAt(0)) {
	    			   if( dfs(board, word.substring(1), row, column)) return true;
				}
			}
		}
		return false;
	}
	private boolean dfs(char[][] board, String word, int row, int column) {
		if (word.length() == 0) {
			return true;
		}
		int height = board.length;
		int length = board[0].length;
		char tem = board[row][column];
		board[row][column] = '~';//用~标记删除,很冒险,因为题中并未说字符串不包含~
		if (row < height - 1&& board[row + 1][column] == word.charAt(0)) {//down
			if(dfs(board, word.substring(1), row + 1, column)) return true;
		} //第一次做,全部用的else if,这是不对的,因为向下不通还需要向下找
		if (column < length - 1&&board[row][column + 1] == word.charAt(0)){//right
			if(dfs(board, word.substring(1), row, 1 + column)) return true;
		} //但是向某一个方向已经走通了,就不需要再迭代了,除非题中要求求出全部路径
		if (row > 0 && board[row - 1][column] == word.charAt(0)) {// get up
			if(dfs(board, word.substring(1), row - 1, column)) return true;
		} 
		if (column > 0 && board[row][column - 1] == word.charAt(0)) {// get left
			if(dfs(board, word.substring(1), row, column - 1)) return true;
		}//如果上下左右都走不通,那就说这个节点是不通的,将删掉的字母添加进去,回溯
		board[row][column] = tem;
		return false;
	}

 

分享到:
评论

相关推荐

    LeetCode最全代码

    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-...

    leetcode苹果-LeetCode_No.208_-:LeetCode_No.208_-

    leetcode 苹果 LeetCode_No.208_-实现 Trie (前缀树) 题目介绍 Trie(发音类似 "try")或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完...

    LeetCode:关于LeetCode.com和ACM的一些算法问题

    LeetCode一些 LeetCode 题目的进阶解法,追求极致效率。由于 LeetCode 已启用中文版域名 leetcode-... Word-Search-II题目: | 英文站源码:./problem-0212-Word-Search-II/标签:哈希表,双向链表难度:困难 / Hard

    leetcode不会-word-search:二维网格中的单词搜索

    leetcode 不会词搜索 给定一个 2D 板和一个单词,查找该单词是否存在于网格中。 单词可以由顺序相邻的单元格的字母构成,其中“相邻”单元格是水平或垂直相邻的单元格。 同一个字母单元格不能多次使用。 Example: ...

    leetcode寻找最近的-leetcode:leetcode题目

    search_word79.cpp。 链表基本操作要进行删除元素,那么在循环的过程中尽量使用前驱进行循环。提前校验head,head-&gt;next。new一个空头部。头插法pcur是空头后一位。 对于查找查找类的题目首先考虑二分查找,但是二分...

    扩展矩阵leetcode-Leetcode:LeetcodeAnswer-Java

    扩展矩阵leetcode Leetcode Leetcode Answer-Java 数组 11.乘最多水容器 ...wordBreak 279.完全平方数 numSquares 排序 56.合并区间 merge 75.颜色分类 sortColors 179.最大数 largestNumber 324.摆

    hihocoder和leetcode-leetcode:leetcode

    hihocoder和leetcode leetcode 目录名 功能 Array 数组 Backtracking 回溯 Bit_Manipulation 位操作 Design 数据结构设计 ...单词搜索:word_search.cpp hihocoder String 文章重排:give_my_text_back.cpp

    leetcode耗时-word-search-ii:查词二

    leetcode 耗时查词二 给定一个 2D 板和字典中的单词列表,找到板中的所有单词。 每个单词必须由顺序相邻单元格的字母构成,其中“相邻”单元格是水平或垂直相邻的单元格。 同一个字母单元格不能在一个单词中多次使用...

    lrucacheleetcode-leetcode:算法实践

    lru缓存leetcode ...数据结构设计https://leetcode.com/problems/add-and-search-word-data-structure-design/ 硬字搜索IIhttps://leetcode.com/problems/word-search-ii/ EasyFind the Difference ...

    leetcode答案-leetcode:leetcode

    Search)+ 鸽笼原理(Pigeonhole Principle) “不允许修改数组” 与 “常数空间复杂度”这两个限制条件意味着:禁止排序,并且不能使用Map等数据结构 小于O(n2)的运行时间复杂度可以联想到使用二分将其中的一个n...

    Python算法题源代码-LeetCode(力扣)-实现 Trie (前缀树)

    boolean search(String word) 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false 。 boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ...

    gasstationleetcode-leetcode:LeetcodeOJ解决方案

    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/...

    word源码java-Awesome-leetcode:leetcode问题的解决方法,包括python和java代码

    word源码java awesome-leetcode 用Java或者python实现的leetcode代码, java相关代码主要来源于 大佬,特此说明,感谢大佬的整理, 我只是为了方便继续写我的python代码,重新更改了许多文件。 Easy # Title Tag 1 ...

    leetcode答案-exercise-book:算法练习记录

    Search 解决方法:DFS LeetCode: 31. Next Permutation 解决方法:掌握排列组合的字典序规律,即可。这个规律找不到,我最后还是直接看答案的。 LeetCode: 581. Shortest Unsorted Continuous Subarray 解决方法:无...

    leetcode添加元素使和等于-Leetcode-Problems-Java-Python--with-Markdown-Explanati

    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, ...

    AlgorithmAndLeetCode#itcharge-LeetCode-Py#0211. 添加与搜索单词 - 数据结构设计

    void addWord(word) 将 word 添加到数据结构中,之后可以对它进行匹配bool search(word) 如果数据结构中存在字符串与 wor

    javalruleetcode-leetcode-python:leetcode问题的Python解决方案

    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力扣是什么-leetcode:leetcodebytags按自己整理的一些类别

    leetcode力扣是什么 leetcode-按类别 看了一些leetcode刷题指南,总结一下两个重点,一是最好按照类别刷题,总结思路;二是由易到难,不要产生太大挫败感。...Search II (hard) DFS /二叉树 the difference between df

    圆和矩形是否重叠leetcode-leetcode_solutions:leetcode_solutions

    圆和椭圆重叠leetcode ——#158 尖端 关心特殊情况 从不同的方向思考 简单的 大批 1.Two Sum -&gt; 使用哈希表避免遍历列表448.查找数组中消失的所有数字-&gt; 1.建立缓冲区来计算数字| 2.使用数组作为带符号的缓冲区118....

    leetcode浇花-LCSolutions:我的力扣解决方案

    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...

Global site tag (gtag.js) - Google Analytics