Word Search(79)

2016-07-04 13:05:00

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 =

[ ['A','B','C','E']
['S','F','C','S'],
['A','D','E','E'] ]

word = "ABCCED", -> returns true, word = "SEE", -> returns true, word = "ABCB", -> returns false.

思路：使用dfs. 先在矩阵中找到word0],若找到，就执行helper函数继续查找。递归结束条件是 index == word.length(); 如果是超过边界或者board[i ！＝ word.charAt(index) 就return false。为防止same letter cell may be used more than once, 要标记已经访问过的letter为 # . 每次递归结束以后还要还原以防影响下一次。

时间复杂度： mn4^(k-1). 也就是mn4^k.
m X n is board size, k is word size.
（脑补题目为从一个字符矩阵中搜索某个字符串是否存在，可以向四个方向延伸。那么dfs和bfs的时间复杂度是指数级别的，大概是4的字符串长度次方，因为每次都可能走四个方向（实际上比这个低，因为不一定四个方向都可以走，也可能走过的地方不能走，但是给出最坏情况就可以了））
空间复杂度： recuision最深是k层，recursive部分空间复杂度应该是O(k)

public class Solution {    public boolean exist(char[][] board, String word) {        for (int i = 0; i = board.length || j >= board[0].length || board[i][j] != word.charAt(index)) {            return false;        }        char tmp = board[i][j];        board[i][j] = '# ';        boolean rst = helper(i + 1, j, index + 1, word, board) || helper(i, j + 1, index + 1, word, board) || helper(i, j - 1, index + 1, word, board) || helper(i - 1, j, index + 1, word, board);        board[i][j] = tmp;        return rst;    }}

关键字：产品经理

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击举报进行投诉反馈！