https://leetcode.com/problems/word-search-ii/

wordSearchII.js

/**
 * @param {character[][]} board
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function(board, words) {
    
    const result = new Set();
    
    const key = (r, c) => `${r}:${c}`;
    const seen = new Set();
    
    const trie = {}; // Could use array but hash easier to work with
    words.forEach((word) => insertWordIntoTrie(word, trie));

    for(let row = 0; row < board.length; row++){
        for(let col = 0; col < board[0].length; col++){
            const c = board[row][col];
            if(trie.hasOwnProperty(c)){
                seen.add(key(row, col));
                search(row, col, trie[c]);
                seen.delete(key(row, col));
            }
        }
    }
    
    return Array.from(result);
    
    // private helpers
    function search(row, col, base){
        
        if(base.terminal) result.add(base.terminal); // found a word!
        
        const adj = [[row+1, col],[row-1, col],[row, col+1],[row, col-1]]
        .forEach(([nr, nc]) => {
            // OOB
            if(nr < 0 || nc < 0 || nr >= board.length || nc >= board[0].length) return;
            
            // Seen before
            const k = key(nr, nc);
            if(seen.has(k)) return;
            
            // matches trie
            const newChar = board[nr][nc];
            if(!base.hasOwnProperty(newChar)) return;
            
            seen.add(k);
            search(nr, nc, base[newChar]);
            seen.delete(k);
        });

    }
};

function insertWordIntoTrie(word, trie, i=0){   
    if(i === word.length) return trie.terminal = word;
    
    const char = word[i];
    
    if(!trie.hasOwnProperty(char)) trie[char] = {};
    insertWordIntoTrie(word, trie[char], i+1);
}