Question

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must 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 in a word.

Example:

Input:
words = ["oath","pea","eat","rain"] and board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Output: ["eat","oath"]

Thinking:

  • Method：TrieTree, dfs
class Solution {    
    public List<String> findWords(char[][] board, String[] words) {
        for(String s : words)
            insert(s);
        Set<String> res = new HashSet<>();
        boolean[][] used = new boolean[board.length][board[0].length];
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                dfs(board, res, new StringBuilder(), i, j, used);
            }
        }
        return new ArrayList<String>(res);
    }
    private void dfs(char[][] board, Set<String> set, StringBuilder sb, int row, int col, boolean[][] used){
        int height = board.length, width = board[0].length;
        if(row >= 0 && row < height && col >= 0 && col < width && !used[row][col]){
            sb.append(board[row][col]);
            String ss = sb.toString();
            if(!hasPrefix(ss)){
                sb.deleteCharAt(ss.length() - 1);
                return;
            }
            if(search(ss)) set.add(ss);
            board[row][col] = true;
            for(int i = 0; i < 4; i++){
                dfs(board, set, sb, row + dir[i][0], col + dir[i][1], used);
            }
            sb.deleteCharAt(sb.toString().length() - 1);
            used[row][col] = false;
        }
    }
    private TrieNode root = new TrieNode();
    private static class TrieNode{
        boolean isLeaf;
        TrieNode[] childs;
        public TrieNode(){
            childs = new TrieNode[26];
        }
    }
    private void insert(String s){
        int len = s.length();
        TrieNode temp = root;
        for(int i = 0; i < len; i++){
            int c = s.charAt(i) - 'a';
            if(temp.childs[c] == null)
                temp.childs[c] = new TrieNode();
            temp = temp.childs[c];
        }
        temp.isLeaf = true;
    }
    private boolean search(String word){
        int len = word.length();
        TrieNode temp = root;
        for(int i = 0; i < len; i++){
            int c = word.charAt(i) - 'a';
            if(temp.childs[c] == null) return false;
            temp = temp.childs[c];
        }
        return temp.isLeaf;
    }
    private boolean hasPrefix(String word){
        int len = word.length();
        TrieNode temp = root;
        for(int i = 0; i < len; i++){
            int c = word.charAt(i) - 'a';
            if(temp.childs[c] == null) return false;
            temp = temp.childs[c];
        }
        return true;
    }
}

二刷

  1. Use DFS to find all words, super slow. 
    class Solution {    
 public List<String> findWords(char[][] board, String[] words) {
     List<String> result = new LinkedList<>();
     if(words == null || words.length == 0) return result;
     int height = board.length, width = board[0].length;
     boolean[][] visited = null;
     Set<String> set = new HashSet<>();
     LABEL:
     for(String word : words){
         if(set.contains(word)) continue;
         set.add(word);
         visited = new boolean[height][width];
         for(int i = 0; i < height; i++){
             for(int j = 0; j < width; j++){
                 char c = word.charAt(0);
                 if(c == board[i][j]){
                     visited[i][j] = true;
                     if(dfs(board, word, 1, height, width, i, j, visited, result))
                         continue LABEL;
                     visited[i][j] = false;
                 }
             }
         }
     }
     return result;
 }
 private boolean dfs(char[][] board, String word, int index, int height, int width, int x, int y, boolean[][] visited, List<String> result){
     if(index == word.length()){
         result.add(word);
         return true;
     }else{
         int tempX, tempY;
         char c = word.charAt(index);
         for(int i = 0; i < 4; i++){
             tempX = x + dir[i][0];
             tempY = y + dir[i][1];
             if(check(board, visited, height, width, tempX, tempY, c)){
                 visited[tempX][tempY] = true;
                 if(dfs(board, word, index + 1, height, width, tempX, tempY, visited, result)){
                     return true;
                 }
                 visited[tempX][tempY] = false;
             }
         }
         return false;
     }
 }
 private boolean check(char[][] board, boolean[][] visited, int height, int width, int x, int y, char c){
     if(x >= 0 && x < height && y >= 0 && y < width && !visited[x][y] && c == board[x][y]){
         return true;
     }
     return false;
 }
}

Third time

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        if(words == null || words.length == 0) return result;
        int height = board.length, width = board[0].length;
        boolean[][] visited = new boolean[height][width];
        Set<String> set = new HashSet<>();
        for(String word: words){
            for(int i = 0; i < height; i++){
                for(int j = 0; j < width; j++){
                    if(board[i][j] == word.charAt(0)){
                        visited[i][j] = true;
                        dfs(board, set, word, i, j, 0, new boolean[height][width]);
                        visited[i][j] = false;
                    }
                }
            }
        }
        result.addAll(set);
        return result;
    }
    private void dfs(char[][] board, Set<String> result, String word, int i, int j, int index, boolean[][] visited){
        if(index == word.length() - 1){
            result.add(word);
        }else{
            visited[i][j] = true;
            int tempRow = 0, tempCol = 0;
            for(int d = 0; d < 4; d++){
                tempRow = i + dir[d][0];
                tempCol = j + dir[d][1];
                if(tempRow >= 0 && tempRow < visited.length && tempCol >= 0 && tempCol < visited[0].length && !visited[tempRow][tempCol] && board[tempRow][tempCol] == word.charAt(index + 1))
                    dfs(board, result, word, tempRow, tempCol, index + 1, visited);
            }
            visited[i][j] = false;
        }
    }
}