212_Word_Search_ii

LeetCode 212: Word Search ii
Detailed Explanation can be found here: https://youtu.be/3PT9QjgYTQc
********************************************************************

C++
----
class Trie{
public:
    Trie* children[26];
    bool endOfWord;
    Trie():endOfWord(false){
        for(int i = 0; i < 26; ++i)
            children[i] = nullptr;
    }
    ~Trie(){
        for(int i = 0; i < 26; ++i)
            if(children[i]) delete children[i];
    }
    
    void insert(string word){
        Trie* curr = this;
        for(char c: word){
            if(!curr->children[c-'a']) curr->children[c - 'a'] = new Trie();
            curr = curr->children[c-'a'];
        }
        curr->endOfWord = true;
    }
};

class Solution {
    void dfs(vector<vector<char>>& board, int i, int j, Trie* trie, unordered_set<string>& result, string s){
        char c = board[i][j];
        if(c == '$') return;
        board[i][j] = '$';
        Trie* t = trie->children[c - 'a'];
        if(t){
            string ss = s + c;
            if(t->endOfWord) result.insert(ss);
            if(i < board.size()-1) dfs(board, i+1, j, t, result, ss);
            if(i > 0) dfs(board, i-1, j, t, result, ss);
            if(j < board[0].size()-1) dfs(board, i, j+1, t, result, ss);
            if(j > 0) dfs(board, i, j-1, t, result, ss);
        }
        board[i][j] = c;
    }
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        if(words.size() == 0) return {};
        Trie trie;
        for(string w: words){
            trie.insert(w);
        }
        
        unordered_set<string> result_s;
        for(int i = 0; i < board.size(); ++i){
            for(int j = 0; j < board[0].size(); ++j){
                dfs(board, i, j, &trie, result_s, "");
            }
        }
        vector<string> result(result_s.begin(), result_s.end());
        return result;
    }
};


Java:
----
class Trie{
    public Trie children[];
    public boolean endOfWord;
    
    public Trie(){
        endOfWord = false;
        children = new Trie[26];
        for(int i = 0; i < 26; ++i)
            children[i] = null;
    }
    
    void insert(String word){
        Trie curr = this;
        for(char c: word.toCharArray()){
            if(curr.children[c-'a'] == null) curr.children[c - 'a'] = new Trie();
            curr = curr.children[c-'a'];
        }
        curr.endOfWord = true;
    }
};

class Solution {
    private void dfs(char[][] board, int i, int j, Trie trie, HashSet<String> result, String s){
        char c = board[i][j];
        if(c == '$') return;
        board[i][j] = '$';
        Trie t = trie.children[c - 'a'];
        if(t != null){
            String ss = s + c;
            System.out.println(ss);
            if(t.endOfWord) result.add(ss);
            if(i < board.length-1) dfs(board, i+1, j, t, result, ss);
            if(i > 0) dfs(board, i-1, j, t, result, ss);
            if(j < board[0].length-1) dfs(board, i, j+1, t, result, ss);
            if(j > 0) dfs(board, i, j-1, t, result, ss);
        }
        board[i][j] = c;
    }
    
    public List<String> findWords(char[][] board, String[] words) {
        if(words.length == 0) return new ArrayList<String>();
        Trie trie = new Trie();
        for(String w: words){
            trie.insert(w);
        }
        
        HashSet<String> result_s = new HashSet();
        for(int i = 0; i < board.length; ++i){
            for(int j = 0; j < board[0].length; ++j){
                dfs(board, i, j, trie, result_s, "");
            }
        }
        List<String> result = new ArrayList(result_s);
        return result;
    }
}


Python3:
-------
class Trie:
    def __init__(self):
        self.endOfWord = False
        self.children = [None]*26
    
    def insert(self, word):
        curr = self
        for c in word:
            idx = ord(c) - ord('a')
            if curr.children[idx] == None: curr.children[idx] = Trie()
            curr = curr.children[idx]
        
        curr.endOfWord = True

class Solution:
    def dfs(self, i, j, trie, s):
        c = self.board[i][j]
        if(c == '$'): return
        self.board[i][j] = '$';
        t = trie.children[ord(c) - ord('a')];
        if(t != None):
            ss = s + c;
            if(t.endOfWord): self.result.add(ss);
            if(i < len(self.board)-1): self.dfs(i+1, j, t, ss);
            if(i > 0): self.dfs(i-1, j, t, ss);
            if(j < len(self.board[0])-1): self.dfs(i, j+1, t, ss);
            if(j > 0): self.dfs(i, j-1, t, ss);
        
        self.board[i][j] = c;
        
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        if len(words) == 0: return []
        self.board = board
        trie = Trie()
        for w in words:
            trie.insert(w)
        
        self.result = set()
        for i in range(len(board)):
            for j in range(len(board[0])):
                self.dfs(i, j, trie, "")
        return list(self.result)