문제

https://leetcode.com/problems/word-search-ii/description/?envType=study-plan-v2&envId=top-interview-150

해결 방법

• 처음에는 words의 단어들을 하나씩 bfs를 돌려 생성할 수 있는지 체크하는 방식으로 시도했음 => words가 최대 30,000개 입력되기 때문에 시간 초과가 발생함
• 따라서 먼저 board에서 만들 수 있는 단어를 dfs를 이용하여 Trie에 삽입 후 words의 단어들을 순회하며 Trie에서 search하는 방식으로 해결
  • 이 때, 시간을 줄이기 위해 words의 단어들을 먼저 조회하며 단어의 길이(최대 10)가 존재한다면 dfs 실행
  • 길이가 10인 단어가 없는데 10짜리 단어들을 모두 Trie에 삽입할 필요가 없기 때문

코드

class Solution {

    private static Trie trie;
    private static final int[] row = new int[]{0, 0, 1, -1};
    private static final int[] col = new int[]{1, -1, 0, 0};

    public List<String> findWords(char[][] board, String[] words) {
        trie = new Trie();
        int m = board.length;
        int n = board[0].length;

        boolean[] lenCheck = new boolean[11];
        int cnt = 0;
        for (String word : words) {
            if (lenCheck[word.length()] == false) {
                lenCheck[word.length()] = true;
                makeTrie(word.length(), m, n, board);
                cnt ++;
            }
            if (cnt == 10) break;
        }

        List<String> answer = new ArrayList<>();
        for (String word : words) {
            if (trie.search(word)) {
                answer.add(word);
            }
        }

        return answer;
    }

    private void makeTrie(int len, int m, int n, char[][] board) {
        for (int i = 0 ; i < m ; i ++) {
            for (int j = 0 ; j < n ; j ++) {
                boolean[][] check = new boolean[m][n];
                check[i][j] = true;
                dfs(i, j, 1, len, board[i][j] + "", board, check);
            }
        }
    }

    private void dfs(int x, int y, int idx, int len, String word, char[][] board, boolean[][] check) {
        if (idx == len) {
            trie.insert(word);
            return;
        }

        for (int i = 0 ; i < 4 ; i ++) {
            int newX = x + row[i];
            int newY = y + col[i];
            if (newX < 0 || newX >= board.length || newY < 0 || newY >= board[0].length) continue;
            if (check[newX][newY]) continue;

            check[newX][newY] = true;
            dfs(newX, newY, idx + 1, len, word + board[newX][newY], board, check);
            check[newX][newY] = false;
        }
    }
}

class Trie {

    private Node root;

    public Trie() {
        this.root = new Node();
    }
    
    public void insert(String word) {
        Node current = this.root;

        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (current.children[idx] == null) {
                current.children[idx] = new Node();
            }
            current = current.children[idx];
        }
        current.isEndOfWord = true;
    }

    public boolean search(String word) {
        Node current = this.root;

        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (current.children[idx] == null) return false;

            current = current.children[idx];
        }

        return current.isEndOfWord;
    }
}

class Node {
    Node[] children;
    boolean isEndOfWord;

    Node() {
        this.children = new Node[26];
        this.isEndOfWord = false;
    }
}

결과