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

思路: Backtracking 的方法来解决这道题目。我们需要先从board中找到第一个字符出现的位置,然后从这个位置开始往上,下,左,右开始寻找;这里我们要借助一个dfs(x,y, index, board, word)的函数来寻找; 当index==word.length的时候就找到了对应的字符,返回true; 注意边界条件的check,x,y要保证在board内,或者当board[x][y]!=word.charAt(index)的时候都返回false。
复杂度: Time复杂度: 遍历整个m * n 的board的时间复杂度为m * n,对于每个点都会往上下左右来遍历寻找, k为word长度,大概要遍历4^k次,所以总的时间复杂度大概在mn4^k.
Space: 由于word长度为k,recursive space大概在O(k).

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board[0] == null || board.length == 0 || board[0].length == 0 || word == null) return false;
        // find the first char of word in board
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (word.charAt(0) == board[i][j]) {
                    if (dfs(i, j, 0, board, word )) {
                        return true;
                    }
                }

            }
        }
        return false;
    }

    public boolean dfs(int x, int y, int index, char[][] board, String word) {
        if (index == word.length()) {
            return true;
        }
        if (x < 0 || y < 0 || x >= board.length || y >= board[0].length || board[x][y] != word.charAt(index)) 
            return false;
        char tmp = board[x][y]; // save the point's value
        board[x][y] = '#'; // mark the point first
        boolean flag = dfs(x - 1, y, index + 1, board, word) ||
                       dfs(x, y - 1, index + 1, board, word) ||
                       dfs(x + 1, y, index + 1, board, word) ||
                       dfs(x, y + 1, index + 1, board, word);
        board[x][y] = tmp;
        return flag;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s