# How to analyze the time/space complexity for this problem?

• public class Solution {
public List<String> findWords(char[][] board, String[] words) {
ArrayList<String> res = new ArrayList<String>();
if (board == null || board.length == 0 || board[0].length == 0) {
return res;
}
HashSet<String> set = new HashSet<String>();
Trie t = new Trie();
for (String item : words) {
t.insert(item);
}
boolean [][]visited = 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, visited, t, i, j, new StringBuilder(), set);
}
}
return new ArrayList<String>(set);
}

``````public void dfs(char[][] board, boolean [][]visited, Trie t, int i, int j, StringBuilder sb, HashSet<String> set) {
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] == true) {
return;
}
sb.append(board[i][j]);
visited[i][j] = true;
String str = sb.toString();
if (t.startsWith(str)) {
if (t.search(str)) {
}
dfs(board, visited, t, i + 1, j, sb, set);
dfs(board, visited, t, i, j + 1, sb, set);
dfs(board, visited, t, i - 1, j, sb, set);
dfs(board, visited, t, i, j - 1, sb, set);
}
visited[i][j] = false;
sb.deleteCharAt(sb.length() - 1);
}

private class Trie{
TrieNode root;

public Trie() {
root = new TrieNode();
}

private class TrieNode{
private char val;
private TrieNode son[];
private boolean isEnd;

public TrieNode() {
son = new TrieNode[26];
isEnd = false;
}
}

public void insert(String word) {
if (word == null || word.length() == 0) {
return;
}
TrieNode node = root;
char[] letters = word.toCharArray();
for (int i = 0; i < word.length(); i++) {
int pos = (int)(letters[i] - 'a');
if (node.son[pos] == null) {
node.son[pos] = new TrieNode();
node.son[pos].val = letters[i];
}
node = node.son[pos];
}
node.isEnd = true;
}

public boolean startsWith(String word) {
if (word == null || word.length() == 0) {
return false;
}
TrieNode node = root;
char []letters = word.toCharArray();
for (int i = 0; i < word.length(); i++) {
int pos = (int)(letters[i] - 'a');
if (node.son[pos] == null) {
return false;
}
node = node.son[pos];
}
return true;
}

public boolean search(String word) {
if (word == null || word.length() == 0) {
return false;
}
TrieNode node = root;
char []letters = word.toCharArray();
for (int i = 0; i < word.length(); i++) {
int pos = (int)(letters[i] - 'a');
if (node.son[pos] == null) {
return false;
}
node = node.son[pos];
}
return node.isEnd;
}
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.