# 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)

```java
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
*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/dfs/tips/212.-word-search-ii-backtracking.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.