Leetcode Word Search II problem solution

class Node:
    def __init__(self, end = 0):
        self.end = end
        self.kids = {}

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        res, root, m, n = set(), Node(0), len(board), len(board[0])
        
        def setTrie(word):
            cur = root
            for w in word:
                if w not in cur.kids:
                    cur.kids[w] = Node()
                cur = cur.kids[w]
            cur.end = 1
            return
        
        def helper(i, j, root, visited, word):
            if root.end == 1: res.add(word)
            visited.add((i, j)) 

            for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                x, y = i + dx, j + dy
                if x < 0 or x >= m or y < 0 or y >= n or (x, y) in visited or board[x][y] not in root.kids: continue
                helper(x, y, root.kids[board[x][y]], visited, word + board[x][y])
            visited.remove((i, j))

            return        
        
        for word in words: setTrie(word)

        for i in range(m):
            for j in range(n):
                if board[i][j] in root.kids: helper(i, j, root.kids[board[i][j]], set(), board[i][j])         
                
        return list(res)

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String s : words) root.add(s, 0);
        Set<String> res = new HashSet<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                find(board, i, j, root.next[board[i][j] - 'a'], res);
            }
        }
        return new ArrayList<>(res);
    }
    
    private void find(char[][] board, int i, int j, TrieNode root, Set<String> res) {
        if (root == null) return;
        if (root.word != null) res.add(root.word);
        char c = board[i][j];
        board[i][j] = 'z' + 1;
        if (i > 0) find(board, i - 1, j, root.next[board[i - 1][j] - 'a'], res);
        if (j > 0) find(board, i, j - 1, root.next[board[i][j - 1] - 'a'], res);
        if (i < board.length - 1) find(board, i + 1, j, root.next[board[i + 1][j] - 'a'], res);
        if (j < board[0].length - 1) find(board, i, j + 1, root.next[board[i][j + 1] - 'a'], res);        
        board[i][j] = c;
    }
    
    class TrieNode {
        TrieNode[] next = new TrieNode[27];
        String word;
        public void add(String s, int index) {
            char c = s.charAt(index);
            if (next[c - 'a'] == null) next[c - 'a'] = new TrieNode();
            if (index + 1 < s.length()) next[c - 'a'].add(s, index + 1);
            else next[c - 'a'].word = s;
        }
    }
}

class Solution {
public:
    bool dfs(vector<vector<char>> &grid, int i, int j, int index, string &word)
    {
        if(i<0 || j<0 || i>=grid.size() || j>=grid[0].size() || grid[i][j]!=word[index] || grid[i][j]=='*')
        return false;

        if(index==word.length()-1)
        return true;

        char c=grid[i][j];
        grid[i][j]='*';
        bool ans=false;

        if( dfs(grid, i+1 ,j ,index+1 ,word) ||
            dfs(grid, i-1 ,j ,index+1 ,word) || 
            dfs(grid, i ,j+1 ,index+1 ,word) || 
            dfs(grid, i ,j-1 ,index+1 ,word))
        ans=true;

        grid[i][j]=c;
        return ans;
    }
    
    vector<string> findWords(vector<vector<char>>& grid, vector<string>& word) {
        
        vector<string> ans;
        for(int a=0;a<word.size();a++) {
            for(int i=0;i<grid.size();i++) {
                int flag=0;
                for(int j=0;j<grid[0].size();j++) {
                    
                    if(word[a][0]==grid[i][j]) {
                        if(dfs(grid,i,j,0,word[a])) {
                            ans.push_back(word[a]);
                            flag=1;
                            break;
                        }
                    }
                }

                if(flag==1)
                break;
            }
        }
        
        return ans;
    }
};