[PS] Leet | 212. 단어 찾기 II

문제

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

예시

Example 1:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

 

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

조건

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] is a lowercase English letter.
• 1 <= words.length <= 3 * 104
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• All the strings of words are unique.

답

단어찾기I 과 같이 각 위치마다 단어검사를 시행하면 O(n^3)의 시간 복잡도를 가지기 때문에 효율이 좋지 못합니다.

 

찾고자 하는 단어들을 Trie 자료 구조로 저장한 뒤,

 

각 위치마다 DFS를 시행하면서 Trie의 자료구조를 읽어나가면 O(n^2)의 시간 복잡도로 해결할 수 있습니다.

/**
 * @param {character[][]} board
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function(board, words) {
    const m = board.length;
    const n = board[0].length;
    const res = [];
    const trie = {data: null};

    // DFS
    const search = (i, j, node) => {
        if (i < 0 || i >= m || j < 0 || j >= n) return
        const char = board[i][j];

        if (char in node){
            const suc = node[char];
            if (suc['data']){
                res.push(suc['data']);
                suc['data'] = null;
            }
            
            board[i][j] = '#'
            search(i+1, j, suc);
            search(i-1, j, suc);
            search(i, j+1, suc);
            search(i, j-1, suc);
            board[i][j] = char;
        }
    }
    
    // Trie 자료구조 초기화
    for (const word of words) {
        let node = trie;
        for (const char of word) {
            if (!(char in node)) node[char] = {data: null};
            node = node[char];
        }
        node['data'] = word;
    }
    
    // 각 위치마다 DFS를 시행하면서 Trie와 값 비교
    for (let i=0; i<m; ++i) {
        for (let j=0; j<n; ++j) {
            search(i, j, trie);
        }
    }

    return res
};