212. Word Search II (backtracking)

如果不用 trie, 可以改成用 set + DFS backtracking

time: O(N*m*n*4^k)

每個字： N

dfs board : mn 次 在4通路出去找（棋盤上每個點都要4方向出去）每個單詞都要4個方向，所以4^k組合

space: O(mn+some set string space)

class Solution {
    private int directions[][] = {{0,1},{1,0},{0,-1},{-1,0}};
    public List<String> findWords(char[][] board, String[] words) {
        
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
            return new ArrayList<>();
        }
        int m = board.length;
        int n = board[0].length;
        
        Set<String> res = new HashSet<>();
        Set<String> wordSet = new HashSet<>();
        Set<String> prefix = new HashSet<>();
        for (String word : words) {
            for (int i = 0; i < word.length(); i++) {
                prefix.add(word.substring(0, i+1));
            }
            wordSet.add(word);
        }
        
        
        boolean visited[][] = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                visited[i][j] = true;
                dfs(res, board, wordSet, prefix, String.valueOf(board[i][j]), visited, i, j);
                visited[i][j] = false;
            }
        }
        
        return new ArrayList<>(res);
    }
    private void dfs(Set<String> res, char[][] board, Set<String> wordSet, Set<String> prefix, String word, boolean visited[][], int i, int j) {
        if (!prefix.contains(word)) {
            return;
        }
        if (wordSet.contains(word)) {
            res.add(word);
        }
        for (int direction[] : directions) {
            int newX = i + direction[0];
            int newY = j + direction[1];
            if (!isInside(board, newX, newY) || visited[newX][newY]) {
                continue;
            }
            visited[newX][newY] = true;
            String newWord = word + String.valueOf(board[newX][newY]);
            dfs(res, board, wordSet, prefix, newWord, visited, newX, newY);
            visited[newX][newY] = false;
        }
    }
    private boolean isInside(char[][] board, int x, int y) {
        return (x >= 0 && x < board.length && y >=0 && y < board[0].length);
    }
}
/*
DFS
if not use trie, 
use set to store prefix

if (word not in prefix) continue; 

DO DFS
*/