212. Word Search II

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

문제

주어진 단어 목록에 있는 단어 중, m x n의 글자 보드에 있는 단어 목록을 반환하자.

• 각 단어는 가로 또는 세로로 인접한 칸의 글자로 이루어져야 한다.
• 같은 글자 칸을 한 단어에 두 번 이상 사용할 수 없다.
• 보드에 있는 글자는 모두 알파벳 소문자이다.
• 주어지는 단어 목록에는 중복을 포함하지 않는다.

입력

• m x n 의 크기의 글자 보드
• 단어 목록

출력

• 글자 보드에 있는 단어 목록

---

나의 풀이

접근

아래 사진과 같이 동, 서, 남, 북 네 방향 모두 탐색해, trie 구조에 넣는 방식을 생각했다. 예를 들면, “oaan” 이라는 단어를 trie 구조에 하나씩 넣는 것이다. 아래에 보이는 방향으로 탐색을 다 했다면, “naao”, “oeii”, “iieo” 이렇게 모든 방향을 고려해 단어를 trie 구조에 넣는다.

모든 단어를 trie 구조에 넣은 후, 주어진 단어 목록의 단어가 있는지 탐색하도록 한다.

시도

위 접근 방식에서 설명했던 사진을 잘 보면, 꼭 직선이 아니라 방향을 꺾어서도 단어를 만들 수 있었다. 하지만, 이 사실을 코드를 다 구현한 뒤, 알았다.

class Solution {
    
    Node root = new Node();

    public List<String> findWords(char[][] board, String[] words) {
        List<String> answer = new ArrayList();

        for (int i = 0; i < board.length; i++) {
            int j = 0;

            Node temp = root;
            for (j = 0; j < board[0].length; j++) {
                int num = board[i][j] - 'a';
                if (temp.nodes[num] == null)
                    temp.nodes[num] = new Node();
                if (j == board[0].length - 1)
                    temp.nodes[num].isEnd = true;
                temp = temp.nodes[num];
            }

            temp = root;
            for (j = board[0].length - 1; j >= 0; j--) {
                int num = board[i][j] - 'a';
                if (temp.nodes[num] == null)
                    temp.nodes[num] = new Node();
                if (j == 0)
                    temp.nodes[num].isEnd = true;
                temp = temp.nodes[num];
            }
        }
        
        for (int i = 0; i < board[0].length; i++) {
            int j = 0;

            Node temp = root;
            for (j = 0; j < board.length; j++) {
                int num = board[j][i] - 'a';
                if (temp.nodes[num] == null)
                    temp.nodes[num] = new Node();
                if (j == board.length - 1)
                    temp.nodes[num].isEnd = true;
                temp = temp.nodes[num];
            }

            for (j = board.length - 1; j >= 0; j--) {
                int num = board[j][i] - 'a';
                if (temp.nodes[num] == null)
                    temp.nodes[num] = new Node();
                if (j == 0)
                    temp.nodes[num].isEnd = true;
                temp = temp.nodes[num];
            }
        }

        for (String s : words) {
            if (root.search(s, 0))
                answer.add(s);
        }

        return answer;
    }

    class Node {
        boolean isEnd;
        Node[] nodes;

        public Node() {
            this.isEnd = false;
            this.nodes = new Node[26];
        }

        public boolean search(String s, int idx) {
            if (idx >= s.length())
                return false;
            
            int i = s.charAt(idx) - 'a';
            
            if (nodes[i] == null)
                return false;
            
            if (nodes[i].isEnd && idx == s.length() - 1)
                return true;
            
            return nodes[i].search(s, idx + 1);
        }
    }
}

• 일단 앞서 설명한 것처럼, 4가지 방향 모두 탐색해 직선 방향으로 만들 수 있는 단어를 trie 구조에 넣도록 하였다.
• 그 후, 주어진 단어 목록에 있는 단어를 하나씩 trie 구조에서 탐색해 있다면 answer 리스트에 넣고, return 했다.

---

다른 풀이

Backtracking + Trie를 이용한 코드이다.

주목해야 할 점

• trie 노드에 isEnd 를 두는 것이 아니라, root부터 해당 노드까지의 글자로 만들 수 있는 word 를 두고 있다.
• trie 구조에 board에 있는 글자가 아닌, 주어진 단어 목록 words에 있는 단어를 저장했다.
• 오히려 tire구조에 있는 단어를 board가 가지고 있는 지 확인하는 느낌
  • board를 DFS 알고리즘을 이용해 탐색하며, trie에 존재하는 지 확인한다.
  • 이미 방문한 board 칸의 값 변경을 이용

public List<String> findWords(char[][] board, String[] words) {
    List<String> res = new ArrayList<>();
    TrieNode root = buildTrie(words);
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            dfs (board, i, j, root, res);
        }
    }
    return res;
}

public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
    char c = board[i][j];
    if (c == '#' || p.next[c - 'a'] == null) return;
    p = p.next[c - 'a'];
    if (p.word != null) {   // found one
        res.add(p.word);
        p.word = null;     // de-duplicate
    }

    board[i][j] = '#';
    if (i > 0) dfs(board, i - 1, j ,p, res); 
    if (j > 0) dfs(board, i, j - 1, p, res);
    if (i < board.length - 1) dfs(board, i + 1, j, p, res); 
    if (j < board[0].length - 1) dfs(board, i, j + 1, p, res); 
    board[i][j] = c;
}

public TrieNode buildTrie(String[] words) {
    TrieNode root = new TrieNode();
    for (String w : words) {
        TrieNode p = root;
        for (char c : w.toCharArray()) {
            int i = c - 'a';
            if (p.next[i] == null) p.next[i] = new TrieNode();
            p = p.next[i];
       }
       p.word = w;
    }
    return root;
}

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    String word;
}