Word Search

dfs, 需要注意的地方是做dfs的时候, 可以建一个visited的2D array; 更快速的方式是将原来的2D Array, 用特殊字符 # 代表已经访问过得节点. 这样节省了空间, 同时速度更快.

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


public boolean dfs(char[][] board, String word, int i, int j){
int m = board.length; int n = board[0].length;
if(i<0 || i>=m || j<0 || j>=n || board[i][j]!=word.charAt(0)) return false;
if(word.length()==1) return true;
if(dfs(board, word.subString(1), i-1, j)) return true;
if(dfs(board, word.subString(1), i+1, j)) return true;
if(dfs(board, word.subString(1), i, j-1)) return true;
if(dfs(board, word.subString(1), i, j+1)) return true;
return false;
}
}
public class Solution {
public boolean exist(char[][] board, String word) {
boolean result = false;
for(int i=0;i<board.length;i++)
for(int j=0;j<board[0].length;j++){
if(dfs(board, i, j, 0, word))
return true;
}
return false;
}


boolean dfs(char[][] board, int i, int j, int k, String word){
if(word.length()==k)
return true;
if(i<0 || i>=board.length || j<0 || j>=board[0].length)
return false;
if(board[i][j]==word.charAt(k)){
char tmp = board[i][j];
board[i][j] = '#';
if(dfs(board, i-1, j, k+1, word) ||dfs(board, i+1, j, k+1, word) || dfs(board, i, j-1, k+1, word) ||dfs(board, i, j+1, k+1, word))
return true;
board[i][j] = tmp;
}
return false;
}


}

Word Search II

这个题, 可以用word search的方式做, 会TLE. 更好的方式是建立Trie, 在当前搜索时, 通过trie node来判断是否有词存在. 如果有, 就继续搜索, 如果没有, 可以停止. 一个关键点是即使搜索到有效词时, 不能停止, 需要继续搜索. 如搜索了"abc", "abcde"可能还存在, 需要继续搜索. 建立Trie时, 记得设isLeaf节点.

public class Solution {
    class TrieNode{
        boolean isLeaf;
        HashMap<Character, TrieNode> children = new  HashMap<Character, TrieNode>();
        public TrieNode(){
        }
    }

    public TrieNode buildTrie(String[] words){
        TrieNode root = new TrieNode();
        for(String word : words){
            TrieNode mover = root;
            for(int i=0;i<word.length();i++){
                char c= word.charAt(i);
                if(!mover.children.containsKey(c)){
                    mover.children.put(c, new TrieNode());
                }
                mover = mover.children.get(c);
                if(i==word.length()-1) mover.isLeaf = true; //after mover move, set leaf
            }
        }
        return root;
    }

    public void dfs(int x, int y, String cur, char[][] board, TrieNode curTrie, List<String> ans){
        if(x<0 || x>=board.length || y<0 || y>=board[0].length || board[x][y]=='#')
            return;
        char c = board[x][y];
        if(!curTrie.children.containsKey(c)) return;
        TrieNode mover = curTrie.children.get(c);
        if(mover.isLeaf){
            if(!ans.contains(cur+c))ans.add(cur+c); //key point don't stop here
        }

        board[x][y] = '#'; //set to be pound
        dfs(x-1, y, cur+c, board, mover, ans);
        dfs(x+1, y, cur+c, board, mover, ans);
        dfs(x, y-1, cur+c, board, mover, ans);
        dfs(x, y+1, cur+c, board, mover, ans);
        board[x][y] = c;

    }

    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = buildTrie(words);
        List<String> ans = new ArrayList<String>();
        for(int i=0;i<board.length;i++)
            for(int j=0;j<board[0].length;j++){
                dfs(i, j, "", board, root, ans);
            }
        return ans;
    }
}