当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

Word Search

发表于: 2015-07-03   作者:hcx2013   来源:转载   浏览:
摘要: 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 ve

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.

 

public class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;
        boolean[][] visit = new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
        	for (int j = 0; j < cols; j++) {
        		if (dfs(board, word, 0, i, j, visit)) {
        			return true;
        		}
        	}
        }
        return false;
    }

	private boolean dfs(char[][] board, String word, int cnt, int rowindex, int colindex,
			boolean[][] visit) {
		if (cnt == word.length()) {
			return true;
		}
		if (rowindex < 0 || colindex < 0 || rowindex >= board.length || colindex >= board[0].length) {
			return false;
		}
		if (visit[rowindex][colindex])  {
			return false;
		}
		if (board[rowindex][colindex] != word.charAt(cnt)) {
			return false;
		}
		visit[rowindex][colindex] = true;
		boolean res = (dfs(board, word, cnt+1, rowindex+1, colindex, visit)
				|| dfs(board, word, cnt+1, rowindex, colindex+1, visit)
				|| dfs(board, word, cnt+1, rowindex-1, colindex, visit)
				|| dfs(board, word, cnt+1, rowindex, colindex-1, visit));
		visit[rowindex][colindex] = false;
		return res;
	}
}

 

Word Search

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
一. 题目描述 Given a 2D board and a word, find if the word exists in the grid. The word can b
题意:实现添加单词和查找单词的作用,即实现字典功能。 思路:'.' 可以代表一个任何小写字母,可能
In Search of Memory, in search of myself ——“In Search of Memory”读后感   感谢pongba的豆
搜索引擎 全文搜索引擎 全文搜索引擎是名副其实的搜索引擎,国外代表有Google,国内则有著名的百度
简介 Bitonic search是一个和binary search比较类似的一种查找方法,不过它的过程会显得稍微复杂一
1. 1d range search -- Range search: find all keys between k1 and k2. -- Range count: number o
搜索引擎 全文搜索引擎 全文搜索引擎是名副其实的搜索引擎,国外代表有Google,国内则有著名的百度
Full Text Hibernate Lucene Search Hello World Example Using Maven and SQLite 17,746 views By
Binary Search Jon Bentley以前说过类似的话:“90%的程序猿无法正确实现二分查找算法 就冲着这句话
The implications of Information Foraging Theory on designing user-centered websites have not
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号