solution

/**
 * @param {character[][]} board
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function(board, words) {
    const trie = new Trie();

    for(let i = 0; i < words.length; i++){
        trie.addWord(words[i]);
    }

    for(let m = 0; m < board.length; m++){
        for(let n = 0; n < board[0].length; n++){
            trie.search(trie.root.children, board, m, n, "");
        }
    }

    return trie.getResult();
};

class TrieNode {
    constructor(){
        this.children = {};
        this.isEndOfWord = false;
    }
}

class Trie{
    constructor(){
        this.root = new TrieNode();
        this.result = [];
    }

    addWord(word){
        let current = this.root;

        for(let char of word){
            if(!current.children[char]){
                current.children[char] = new TrieNode();
            }

            current = current.children[char];
        }

        current.isEndOfWord = true;
    }

    search(node, board, m, n, str){
        // board를 빠져나가는 상황
        if(m < 0 || m >= board.length || n < 0 || n >= board[0].length){
            return;
        }

        // 현재 node에서 해당 글자로 갈 수 없는 경우
        if(!node[board[m][n]]){
            return;
        }

        str += board[m][n];
        node = node[board[m][n]];

        const char = board[m][n];

        // 지나간 board임을 표시
        board[m][n] = "@";

        if(node.isEndOfWord){
            this.result.push(str);
            // 한번 성공한 문자열에 대해서는 지워줄 필요가 있음.
        	// ex) "oa", "oaa" => "oa"가 두 번 생성되는 문제 발생
	        // words에 들어있는 문자열은 한번씩만 생성되어야함.
            // 그런데 words에서 직접 삭제하는 것은 안되니까
            // isEndOfWord를 false로 바꿔서 다시 이 단어가 구성되지 못하도록 한다.
            node.isEndOfWord = false;
        }

        this.search(node.children, board, m, n+1, str);
        this.search(node.children, board, m, n-1, str);
        this.search(node.children, board, m-1, n, str);
        this.search(node.children, board, m+1, n, str);

        // 하나의 word에 대한 연산이 끝났으므로 지나감 표시를 초기화.
        board[m][n] = char;
    }
    
    getResult(){
        return this.result;
    }
}

이 문제는 가능한 모든 경로를 탐색하는 DFS를 사용하는 것이 핵심이라고 생각된다.

문자열을 다루는 문제였기 때문에 words에 담긴 단어들을 모두 Trie에 생성해주는 과정을 거쳤다.
이렇게 생성된 Trie를 board의 알파벳들을 순회하면서 DFS를 진행하면서 생성 가능한 문자인지 판단하면 된다.

base case를 통과하면 문자열을 구성해 나갈 수 있는 상태이므로,
str에 지금까지 만들어진 문자열을 담는다.
그 후, node를 해당 문자열의 node도 전환한다.
전환이라고는 하지만 자식 Trie에서 자식 node로 이동하는 것이다.
즉, DFS를 진행 중이라고 생각하면 편하다.

또한, board에서 한번 지나간 알파벳은 다시 사용할 수 없으므로 다른 기호를 써서 표시를 해준다.
문제 조건으로 알파벳만 나온다고 했으므로, 특수 기호 @를 사용하여 지나갔다는 것을 표시했다.

마지막으로 현재 node가 isEndOfWord를 true로 가지고 있다면, 생성할 수 있는 문자열을 얻은 것이므로 result에 추가한다.
여기서 중요한 것이 있는데, result에 추가한 뒤에 해당 node의 isEndOfWord를 false로 바꿔줘야 한다는 것이다!
주석에도 적어놨지만 이 작업을 하지 않으면, 예외 케이스에서 result에 중복 답안이 생성될 수 있다.

이제 탐색 외의 상황에 대해서는 모두 처리를 했으니, board에서 상하좌우를 순회하며 DFS를 진행하면 된다.

DFS가 마무리되면 words에 존재하는 하나의 단어에 대한 search가 끝났으므로,
board를 다시 원래대로 되돌려서 다른 단어들의 search에 사용할 수 있게 복구해준다.

다른 분의 solution

const findWords = (board, words) => {
  const dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]];
  let res = [];

  const buildTrie = () => {
    const root = {};
    for (const w of words) {
      let node = root;
      for (const c of w) {
        if (node[c] == null) node[c] = {};
        node = node[c];
      }
      node.word = w;
    }
    return root;
  };

  const search = (node, x, y) => {
    if (node.word != null) {
      res.push(node.word);
      node.word = null; // make sure only print one time for each word
    }

    if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) return;
    if (node[board[x][y]] == null) return;

    const c = board[x][y];
    board[x][y] = '#'; // Mark visited
    for (const [dx, dy] of dirs) {
      const i = x + dx;
      const j = y + dy;
      search(node[c], i, j);
    }
    board[x][y] = c; // Reset
  };

  const root = buildTrie();
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      search(root, i, j);
    }
  }
  return res;
};

이 분도 필자와 동일한 로직을 사용하셨다.
다만, class가 아니라 일반 함수를 사용하셨고, 문제로 주어진 함수 내부에 작성하셔서,
불필요한 인자를 전달하지 않는다는 것이 깔끔해보인다.
Trie를 생성하는 방법이 상당히 독특한데,
필자가 isEndOfWord를 사용하여 Trie에서 생성할 수 있는 문자열을 기록한 반면,
word라는 속성을 설정하여 문자열을 그대로 사용하셨다.
개인적으로는 Trie를 어떻게 사용한건지 알아보기 힘들었다.
아무래도 isEndOfWord를 사용하는 것이 더 알아보기 쉬운 것 같다.
그 외 로직에서는 일반적인 방법과 다르지 않게 접근하신 것 같다.