[LeetCode] 212. Word Search II

😎풀이

1. 단어를 찾는 문제이며 각 문자를 기준으로 단어가 생성될 수 있으므로 Trie 자료구조를 생성한다.
2. 입력(insert)이 주어질 경우 각 자식 노드로 이동해가며 문자가 완성되는 시점의 노드에는 해당 문자가 무엇이였는지 기록한다. (중복이 없기에 문제되지 않음)
3. board를 순회하며 해당 문자열을 기준으로 주변 노드를 탐색하며 완성되는 문자를 result에 추가한다.
4. result를 반환하여 완성이 가능한 문자를 반환한다.

class TrieNode {
    children: { [key: string]: TrieNode } = {};
    word: string | null = null;
}

class Trie {
    root: TrieNode = new TrieNode();

    insert(word: string): void {
        let node = this.root;
        for (const char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.word = word;
    }
}

function findWords(board: string[][], words: string[]): string[] {
    const trie = new Trie();
    for (const word of words) {
        trie.insert(word);
    }

    const result: string[] = [];
    const rows = board.length;
    const cols = board[0].length;
    const directions = [
        [0, 1], [1, 0], [0, -1], [-1, 0] // 우, 하, 좌, 상
    ];

    function backtrack(node: TrieNode, r: number, c: number) {
        const char = board[r][c];
        if (!node.children[char]) return;

        node = node.children[char];
        if (node.word) {
            result.push(node.word);
            node.word = null; // 중복 저장 방지
        }

        board[r][c] = '#'; // 방문 표시
        for (const [dr, dc] of directions) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] !== '#') {
                backtrack(node, nr, nc);
            }
        }
        board[r][c] = char; // 원상 복구
    }

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            backtrack(trie.root, r, c);
        }
    }

    return result;
}