Word Search

这道题其实就是直接用dfs做即可,刚开始我想用一个非recursive的dfs,用stack来做,最后发现追踪visited和child太麻烦了,最后还是换用recursive的方法,代码比较straight forward,只需对每个元素做DFS即可。
另外做dfs的时候需要用一个visited的数据结构来保存已经visit过的地方,以免重复计算dfs已经step过的地方,刚开始是用一个Hashset,因为存的是二维Node的新的Class,所以需要overload equals和hashCode两个function,这样好像会增加overhead,最后大集合超时,最后还是要用二维的visited数组来解决。

public class Solution {
    public boolean exist(char[][] board, String word) {
        HashSet<Node> visited = new HashSet<Node>();
        if (board.length == 0 || word.length() == 0)
            return false;
        for (int i = 0; i < board.length; i++)
        {
            for (int j = 0; j < board[0].length; j++)
            {
                if (board[i][j] == word.charAt(0))
                    if (dfs(board, word, i, j, 0, visited))
                        return true;
            }
        }
        return false;
    }
    
    public boolean dfs(char[][] board, String word, int r, int c, int i, HashSet<Node> visited)
    {
        if (i == word.length()-1)
            return true;
        i++;
        boolean findNext = false;
        Node curr = new Node(r, c);
        visited.add(curr);
        if (curr.r - 1 >= 0)
            if (!visited.contains(new Node(curr.r - 1, curr.c)) && board[curr.r - 1][curr.c] == word.charAt(i))
            {
                if ( i == word.length() - 1)
                    return true;
                findNext |= dfs(board, word, curr.r - 1, curr.c, i+1, visited);
            }
        if (curr.r + 1 < board.length)
            if (!visited.contains(new Node(curr.r + 1, curr.c)) && board[curr.r + 1][curr.c] == word.charAt(i))
            {
                if ( i == word.length() - 1)
                    return true;
                findNext |= dfs(board, word, curr.r + 1, curr.c, i+1, visited);
            }
        if (curr.c - 1 >= 0)
            if (!visited.contains(new Node(curr.r, curr.c - 1)) && board[curr.r][curr.c - 1] == word.charAt(i))
            {
                if ( i == word.length() - 1)
                    return true;
                findNext |= dfs(board, word, curr.r, curr.c - 1, i+1, visited);
            }    
        if (curr.c + 1 < board[0].length)
            if (!visited.contains(new Node(curr.r, curr.c + 1)) && board[curr.r][curr.c + 1] == word.charAt(i))
            {
                if ( i == word.length() - 1)
                    return true;
                findNext |= dfs(board, word, curr.r, curr.c + 1, i+1, visited);
            }
        visited.remove(curr); // important, it poped from stack ,remove it from visited 
        return findNext;
    }
}

class Node
{
    int r;
    int c;
    public Node(int r, int c)
    {
        this.r = r;
        this.c = c;
    }
    @Override
    public boolean equals(Object n)
    {
    	if (!(n instanceof Node))	
    		return false;
    	Node t = (Node)n;
    	if (t.r == this.r && t.c == this.c)
    		return true;
    	return false;
    }
    @Override
    public int hashCode() {
    	return (c * r); //bad hash function
    }
}

最后参考网上答案,发现其实用recursive的写法可以如此简单

public class Solution {
    public boolean exist(char[][] board, String word) {
        boolean [][] visited = new boolean [board.length][board[0].length];
        if (board.length == 0 || word.length() == 0)
            return false;
        for (int i = 0; i < board.length; i++)
        {
            for (int j = 0; j < board[0].length; j++)
            {
                if (dfs(board, word, i, j, 0, visited))
                    return true;
            }
        }
        return false;
    }
    
    public boolean dfs(char[][] board, String word, int r, int c, int i, boolean [][] visited)
    {
        if (i == word.length())
            return true;
        if (r < 0 || c < 0 || r >board.length-1 || c > board[0].length - 1 || visited[r][c] || board[r][c] != word.charAt(i))
            return false;
        visited[r][c] = true;
        boolean findNext =  dfs(board, word, r - 1, c, i+1, visited)
                            || dfs(board, word, r + 1, c, i+1, visited)
                            || dfs(board, word, r, c - 1, i+1, visited)
                            || dfs(board, word, r, c + 1, i+1, visited);
        visited[r][c] = false;; // important, it poped from stack ,remove it from visited 
        return findNext;
    }
}

Second Submission:

Always remember to include the visited vector(matrix) to record the visited nodes to avoid duplicate scanning

public class Solution {
    public boolean exist(char[][] board, String word) {
        boolean [][] visited = new boolean [board.length][board[0].length];
        if (board.length == 0)
            return word.length() == 0;
        for (int r = 0 ; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                if (dfs(board, word, r, c, visited))
                    return true;
            }
        }
        return false;
    }
    
    public boolean dfs(char[][] board, String word, int r, int c, boolean [][] visited) {
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || visited[r][c])
            return false;
        if (word.length() == 1)
            return board[r][c] == word.charAt(0);
        else {
            if (word.charAt(0) == board[r][c]) {
                visited[r][c] = true;
                boolean result = (dfs(board, word.substring(1), r+1, c, visited) ||
                                 dfs(board, word.substring(1), r-1, c, visited) ||
                                 dfs(board, word.substring(1), r, c+1, visited) ||
                                 dfs(board, word.substring(1), r, c-1, visited));
                visited[r][c] = false;
                return result;
            }
            else 
                return false;
        }
    }
}

Same idea, different code

public class Solution {
    public boolean exist(char[][] board, String word) {
        boolean [][] visited = new boolean [board.length][board[0].length];
        if (board.length == 0)
            return word.length() == 0;
        for (int r = 0 ; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                if (dfs(board, word, r, c, visited))
                    return true;
            }
        }
        return false;
    }
    
    public boolean dfs(char[][] board, String word, int r, int c, boolean [][] visited) {
        if (word.length() == 1)
            return board[r][c] == word.charAt(0);
        String next = word.substring(1);
        visited[r][c] = true;
        if (r > 0 && !visited[r-1][c])
            if (dfs(board, next, r-1, c, visited))
                return true;
        if (r < board.length-1 && !visited[r+1][c]) 
            if (dfs(board, next, r+1, c, visited))
                return true;
        if (c > 0 && !visited[r][c-1])
            if (dfs(board, next, r, c-1, visited))
                return true;
        if (c < board[0].length-1 && !visited[r][c+1])
            if (dfs(board, next, r, c+1, visited))
                return true;
        visited[r][c] = false;
        return false;
    }
}

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