212. Word Search II - Streak 15

보드의 크기는 최대 12x12로, 순수하게 DFS를 수행한다면 4^144의 시간복잡도가 된다.

 

하지만 문제의 제약조건을 잘 살펴보면, 단어의 길이가 최대 10자인 것을 확인할 수 있고, 즉 우리는 최대 10개의 글자만 살펴보면 된다.

 

이는 DFS의 과정이 O(4^10) 으로 제한됨을 의미한다.
이를 보드의 각 칸(144개의 칸)에 수행해보면 된다.

 

그렇다면 이제 각 단어가 실제로 존재하는지를 매칭해보면 되는데, 확인해봐야 하는 단어는 총 3만개이다.
이를 일일히 매칭해보는 것은 당연히 시간초과일 것이다.

 

그래서 word를 해시맵으로 바꾸는 것도 생각해볼 수 있다.
하지만 이번엔 단순히 Trie를 이용하는 방식을 선택했다.

트라이를 사용하게 되면, 해시맵을 이용한 완전탐색과 달리 트라이 아래에 더이상 노드가 존재하지 않을 때, 백트래킹으로 순회를 중단할 수 있다.

class Solution {
    int[] dx = new int[]{0, 0, -1, 1};
    int[] dy = new int[]{-1, 1, 0, 0};
    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for(int i = 0; i<words.length; i++){
            TrieNode node = root;
            for(int j = 0; j<words[i].length(); j++){
                node = node.children.computeIfAbsent(words[i].charAt(j), k -> new TrieNode());
            }
            node.word = words[i];
        }

        int n = board.length;
        int m = board[0].length;
        List<String> ret = new ArrayList<>();
        boolean[][] check = new boolean[n][m];
        for(int i = 0; i<n; i++){
            for(int j = 0; j<m; j++){
                check[i][j] = true;
                dfs(i, j, 10, root, board, check, ret);
                check[i][j] = false;
            }
        }
        return ret;
    }
    private void dfs(int x, int y, int remain, TrieNode node, char[][] board, boolean[][] check, List<String> ret){
        if(remain == 0) return;
        node = node.children.get(board[x][y]);
        if(node == null) return;
        if(node.word != null){
            ret.add(node.word);
            node.word = null;
        }
        for(int k = 0; k<4; k++){
            int p = x + dx[k];
            int q = y + dy[k];
            if(p < 0 || p >= board.length || q < 0 || q >= board[0].length) continue;
            if(check[p][q]) continue;
            check[p][q] = true;
            dfs(p, q, remain-1, node, board, check, ret);
            check[p][q] = false;
        }
    }
}
class TrieNode{
    public String word;
    public Map<Character, TrieNode> children = new HashMap<>();
    public TrieNode(){}
}